题目描述

数列 $a_0,\ a_1,\ a_2,\ \dots$ の一般項 $a_n$ を次のように定義します。

$ a_n\ =\ \begin{cases}\ 1\ &\ (0\ \leq\ n\ \lt\ 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}$ はビット単位 AND)

ビット単位 AND とは？ 整数 $A,B$ のビット単位 AND、$A\text{\ AND\ }B$ は以下のように定義されます。
・$A\text{\ AND\ }B$ を二進表記した際の $2^k$ $(k\ \geq\ 0)$ の位の数は、$A,B$ を二進表記した際の $2^k$ の位の数のうち両方が $1$ であれば $1$、そうでなければ $0$ である。

输入格式

入力は以下の形式で標準入力から与えられる。

$K$ $N$

输出格式

答えを出力せよ。

题目大意

给定正整数 $k$，定义线性递推数列：

$$a_n = \begin{cases} 1 \ , \ (0 \leq n < k) \\ \displaystyle\sum_{i=1}^k a_{n-i} \ , \ (n \geq k)\end{cases} $$

再给定 $n$，对所有「二进制下与 $n$ 的按位与运算后为自身」的自然数 $m$，求 $a_m$ 之和。

比如 $k=2$，$n=6$ 时满足条件的 $m$ 有 $2,4,6$，可以计算出 $a_2+a_4+a_6=21$。

2 6

21

2 8

35

1 123456789

65536

300 20230429

125461938

42923 999999999558876113

300300300

提示

制約

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

Sample Explanation 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$ になります。