题目描述

我们定义序列 $a_0, a_1, a_2, \dots$ 的通项公式为：

$a_n = \begin{cases} 1 & (0 \leq n < K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n). \\ \end{cases}$

给定一个整数 $N$，找到满足 $m \text{ AND }N = m$ 的所有非负整数 $m$ 对应的 $a_m$ 的和（对模 $998244353$ 取余）。这里的 $\text{AND}$ 表示按位与操作。

什么是按位与？非负整数 $A$ 和 $B$ 的按位与 $A \text{ AND }B$ 定义如下：

• 当 $A \text{ AND }B$ 的二进制表示中的第 $2^k$ 位（$k \geq 0$）为 $1$ 时，仅当 $A$ 和 $B$ 的相应的第 $2^k$ 位都为 $1$ 时，该位为 $1$，否则为 $0$。

约束条件

• $1 \leq K \leq 5 \times 10^4$
• $0 \leq N \leq 10^{18}$
• $N$ 和 $K$ 是整数。

输入

输入以以下格式从标准输入中给出：

$K$ $N$

输出

输出作为一个整数。

示例输入 1

2 6

示例输出 1

21

$a_m$ 的值依次为 $1, 1, 2, 3, 5, 8, 13, 21, \dots$。对于满足 $6 \text{ AND }m = m$ 的非负整数 $m$，有 $0, 2, 4, 6$，所以答案为 $1 + 2 + 5 + 13 = 21$。

示例输入 2

2 8

示例输出 2

35

示例输入 3

1 123456789

示例输出 3

65536

示例输入 4

300 20230429

示例输出 4

125461938

示例输入 5

42923 999999999558876113

示例输出 5

300300300