题目描述

数列 $a_0,\ a_1,\ a_2,\ \dots$ 的通项 $a_n$ 定义如下：

$$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$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数值为 $A,B$ 的二进制表示中第 $2^k$ 位都为 $1$ 时为 $1$，否则为 $0$。

输入格式

输入从标准输入读取，格式如下：

$K$ $N$

输出格式

请输出答案。

样例 1

输入

2 6

输出

21

样例 2

输入

2 8

输出

35

样例 3

输入

1 123456789

输出

65536

样例 4

输入

300 20230429

输出

125461938

样例 5

输入

42923 999999999558876113

输出

300300300

说明/提示

限制条件

• $1 \leq K \leq 5 \times 10^4$
• $0 \leq N \leq 10^{18}$
• $N, K$ 均为整数

样例解释 1

数列各项从 $a_0$ 开始依次为 $1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \dots$。满足 $6\ \text{AND}\ m = m$ 的非负整数有 $0,\ 2,\ 4,\ 6$ 共 $4$ 个，因此答案为 $1 + 2 + 5 + 13 = 21$。

由 ChatGPT 4.1 翻译