题目描述

Yuki 是一个喜欢研究数字的数学家！

Yuki 定义，$k$ 进制正整数 $n$ 的翻转数 $R_k(n)$ 为 $n$ 在 $k$ 进制下的所有数字以相反顺序写出来并舍去前导零后得到的 $k$ 进制数。

例如，$R_{10}(521)=125$，$R_2(10110)=1101$。

现在，Yuki 有一个十进制正整数 $k$ 和一个 $k$ 进制正整数 $n$，她想让你求出有多少个不大于 $n$ 的 $k$ 进制正整数 $x$ 满足 $R_k(x)$ 是 $x$ 的倍数。你需要用十进制输出答案，并且答案需要对 $998244353$ 取模。

输入格式

第一行包含一个十进制正整数 $k$。

第二行包含一个 $k$ 进制正整数 $n$（$10,11,12,13,14,15$ 分别用大写字母 $\texttt A,\texttt B,\texttt C,\texttt D,\texttt E,\texttt F$ 表示）。

输出格式

输出一行，包含一个十进制整数，表示满足条件的正整数 $x$ 的数量对 $998244353$ 取模后的结果。

样例 1 输入

10
9999

样例 1 输出

200

样例 1 解释

$R_{10}(1089)=9801=9\times1089$，$R_{10}(2178)=8712=4\times2178$，所以这两个数都满足要求；而剩余满足要求的数都满足 $R_{10}(x)=x$，其中四位数和三位数各有 $90$ 个，两位数和一位数各有 $9$ 个，一共有 $90+90+9+9+2=200$ 个。

样例 2

见下发文件中的 $\textit{reverse/reverse2.in}$ 与 $\textit{reverse/reverse2.ans}$。

该组样例满足测试点 $4$ 的限制。

样例 3

见下发文件中的 $\textit{reverse/reverse3.in}$ 与 $\textit{reverse/reverse3.ans}$。

该组样例满足测试点 $7$ 的限制。

样例 4

见下发文件中的 $\textit{reverse/reverse4.in}$ 与 $\textit{reverse/reverse4.ans}$。

该组样例满足测试点 $10$ 的限制。

样例 5

见下发文件中的 $\textit{reverse/reverse5.in}$ 与 $\textit{reverse/reverse5.ans}$。

该组样例满足测试点 $14$ 的限制。

样例 6

见下发文件中的 $\textit{reverse/reverse6.in}$ 与 $\textit{reverse/reverse6.ans}$。

该组样例满足测试点 $18$ 的限制。

样例 7

见下发文件中的 $\textit{reverse/reverse7.in}$ 与 $\textit{reverse/reverse7.ans}$。

该组样例满足测试点 $25$ 的限制。

数据范围

对于所有测试数据，保证：

• $2 \le k \le 16$；
• $1 \le n \lt k^{10^5}$。