T388306 K

很遗憾，在一次测试中 JJY 写的斗地主 bot 寄掉了。  它遇到了一个很奇怪的 bug。在打斗地主时，LYY 打出了一张`K`，没有人要的起，但 bot 内部的某段含有 `K` 个字母 `K` 的代码和这张 `K` 发生了某种不知名错误，使 bot 寄掉了。JJY 现在正在紧（gu）急（gu）地（gu）修（gu）复（gu）它。

给定一个 $16$ 进制数 $N$，求 $1$ 到 $N$ 中数字 $k$ 出现了几次。 答案对 $99999989$ 取余。

第一行两个数， 第一个数为十进制数 $L$，表示数字 $N$ 的位数；第二个数为一位十六进制数 $k$，代表要找的数字。 第二行一个十六进制数 $N$。

一个十进制整数，表示 $1$ 到 $N$ 中数字 $k$ 出现的次数对 $99999989$ 取余的答案。

**样例 1 解释** 从 $\texttt{1}$ 到 $\texttt{2A}$ 有 $\texttt{1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,}$ $\texttt{10,11,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E,1F,}$ $\texttt{20,21,22,23,24,25,26,27,28,29,2A}$ 这些数字，其中数字 $\texttt{2}$ 出现了 $14$ 次。 **样例 2 解释** 从 $\texttt{1}$ 到 $\texttt{FF}$ 的所有数字中含 $\texttt{A}$ 的数字有 $\texttt{A,1A,2A,3A,4A,5A,6A,7A,8A,9A,}$ $\texttt{A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,AA,AB,AC,AD,AE,AF,}$ $\texttt{BA,CA,DA,EA,FA}$， 其中出现了 $32$ 个 $\texttt{A}$。 **数据范围** 对于 $10\%$ 的数据，$L \leq 5$。 对于 $25\%$ 的数据，$L \leq 100$。 对于 $50\%$ 的数据，$L \leq 5000$。 对于 $100\%$ 的数据，$1 \leq L \leq 10^6$。 且其中有 $20\%$ 的数据，$N=16^{L+1}-1$。 $K$ 为一位十六进制数，范围 $1～F$，前导零不计入计算。 $\texttt{ps:}$这道题的 std 被神[@LYYY](https://www.luogu.com.cn/user/108033)爆杀，原来的 std 变成 50pts 暴力，于是经过 sb 出题人的自我 push 后寻找到了更优解，数据得以加强。