冗余二进制表示法与二进制表示法类似，不同之处在于，我们允许每一位上的数字取 $[0, t]$ 范围内的任意整数，其中 $t$ 是给定的上界。例如，若 $t = 2$，则允许数字 $2$ 出现，此时十进制数 $4$ 可以写作 $100$、$20$ 或 $12$。若 $t = 1$，则每个数都有且仅有一种表示方式，即其标准的二进制表示。一般地，如果一个数在冗余二进制表示法中写作 $d_l d_{l-1} \dots d_1 d_0$，则其对应的十进制数值为 $d_l \cdot 2^l + d_{l-1} \cdot 2^{l-1} + \dots + d_1 \cdot 2^1 + d_0 \cdot 2^0$。

冗余二进制表示法可以实现无进位算术，因此在硬件设计甚至最坏情况数据结构的设计中都有应用。例如，考虑标准二项堆的插入操作。该操作的最坏情况时间复杂度为 $O(\log n)$，但均摊时间复杂度为 $O(1)$。这是因为表示堆中元素总数的二进制数可以在 $O(\log n)$ 的最坏情况下递增，且均摊时间复杂度为 $O(1)$。通过在二项堆中使用各个二项树的冗余二进制表示，可以将二项堆的最坏情况插入时间改进为 $O(1)$。

然而，上述信息与本题无关。本题的任务很简单：给定一个十进制数 $N$ 和数字上界 $t$，请计算 $N$ 在冗余二进制表示法下，每一位数字均在 $[0, t]$ 范围内且无前导零的表示方式的数量。

输入格式

输入包含一行，由两个十进制整数 $N$ ($0 \le N \le 10^{16}$) 和 $t$ ($1 \le t \le 100$) 组成，中间以空格分隔。

输出格式

输出十进制数 $N$ 在冗余二进制表示法下，每一位数字均在 $[0, t]$ 范围内且无前导零的表示方式的数量。由于表示方式的数量可能非常大，请将结果对大质数 $998\,244\,353$ 取模后输出。

样例

样例输入 1

4 2

样例输出 1

3

样例输入 2

6 3

样例输出 2

4

样例输入 3

479 1

样例输出 3

1

样例输入 4

3846927384799 62

样例输出 4

690163857

样例输入 5

549755813887 2

样例输出 5

1