← 返回题目列表

AtCoder · abc300_h

Ex. 斐波那契:重温

中文机器翻译题面 查看原题

分数: 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