分数: 600 点
问题陈述
我们定义通用术语 序列的 a_n 一个序列的 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,求总和,取模 998244353,属于 a_m 所有非负整数 m 这样 m\text{ AND }N = m. (\text{AND} 表示按位与。)
什么是按位与?
非负整数的按位与 A 和 B, A\text{ AND }B定义如下。、正确 A\text{ AND }B 以二进制形式写入,其 2^k的地方 (k \geq 0) 是 1 if 2^k的地方 A 和 B 都是 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_0 和后续术语是 1, 1, 2, 3, 5, 8, 13, 21, \dots。 四个非负整数, 0, 2, 4,和 6,满足 6 \text{ AND } m = m,所以答案是 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