斐波那契:再探

题目描述

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

$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}$ 表示按位与。)

什么是按位与?

非负整数 $A$ 和 $B$ 的按位与 $A\text{ AND }B$ 定义如下。

用二进制表示 $A\text{ AND }B$ 时,若 $A$ 和 $B$ 的 $2^k$ 位($k \geq 0$)都为 $1$,则结果的 $2^k$ 位为 $1$,否则为 $0$。

输入格式

输入按以下格式从标准输入给出:

$K$ $N$

输出格式

输出答案。

样例

2 6

21

$a_0$ 及其后的各项为 $1, 1, 2, 3, 5, 8, 13, 21, \dots$。 满足 $6 \text{ AND } m = m$ 的非负整数有 $0, 2, 4, 6$ 四个,因此答案为 $1 + 2 + 5 + 13 = 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$ 为整数。