Yuki is a mathematician who loves studying numbers!

Yuki defines the reversal $R_k(n)$ of a positive integer $n$ in base $k$ as the number obtained by writing the digits of $n$ in base $k$ in reverse order and removing any leading zeros.

For example, $R_{10}(521)=125$ and $R_2(10110)=1101$.

Now, Yuki has a positive integer $k$ in base 10 and a positive integer $n$ in base $k$. She wants you to find how many positive integers $x$ in base $k$ such that $x \le n$ satisfy the condition that $R_k(x)$ is a multiple of $x$. You need to output the answer in base 10, modulo $998244353$.

Input

The first line contains a positive integer $k$ in base 10.

The second line contains a positive integer $n$ in base $k$ (where $10, 11, 12, 13, 14, 15$ are represented by the uppercase letters $\texttt A, \texttt B, \texttt C, \texttt D, \texttt E, \texttt F$ respectively).

Output

Output a single integer in base 10, representing the number of positive integers $x$ that satisfy the condition, modulo $998244353$.

Examples

Input 1

10
9999

Output 1

200

Note 1

$R_{10}(1089)=9801=9\times1089$ and $R_{10}(2178)=8712=4\times2178$, so both these numbers satisfy the condition. The remaining numbers that satisfy the condition are those where $R_{10}(x)=x$. There are $90$ such four-digit numbers, $90$ three-digit numbers, $9$ two-digit numbers, and $9$ one-digit numbers. In total, there are $90+90+9+9+2=200$ such numbers.

Input 2

See the files $\textit{reverse/reverse2.in}$ and $\textit{reverse/reverse2.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 4.

Input 3

See the files $\textit{reverse/reverse3.in}$ and $\textit{reverse/reverse3.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 7.

Input 4

See the files $\textit{reverse/reverse4.in}$ and $\textit{reverse/reverse4.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 10.

Input 5

See the files $\textit{reverse/reverse5.in}$ and $\textit{reverse/reverse5.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 14.

Input 6

See the files $\textit{reverse/reverse6.in}$ and $\textit{reverse/reverse6.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 18.

Input 7

See the files $\textit{reverse/reverse7.in}$ and $\textit{reverse/reverse7.ans}$ in the provided materials.

This sample case satisfies the constraints of test case 25.

Constraints

For all test cases, it is guaranteed that:

• $2 \le k \le 16$;
• $1 \le n \lt k^{10^5}$.