Score : $600$ points

问题陈述

我们通过以下方式定义序列 $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$。

什么是按位与（bitwise AND）？两个非负整数 $A$ 和 $B$ 的按位与运算 $A\text{ AND }B$ 定义如下： ・当以二进制表示 $A\text{ AND }B$ 时，其在 $2^k$ 位上（$k \geq 0$）的值为 $1$，当且仅当 $A$ 和 $B$ 在 $2^k$ 位上都为 $1$，否则为 $0$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We define the general term $a_n$ of a sequence $a_0, a_1, a_2, \dots$ by:

$a_n = \begin{cases} 1 & (0 \leq n \lt K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n). \\ \end{cases}$

Given an integer $N$, find the sum, modulo $998244353$, of $a_m$ over all non-negative integers $m$ such that $m\text{ AND }N = m$. ($\text{AND}$ denotes the bitwise AND.)

What is bitwise AND? The bitwise AND of non-negative integers $A$ and $B$, $A\text{ AND }B$, is defined as follows.
・When $A\text{ AND }B$ is written in binary, its $2^k$s place ($k \geq 0$) is $1$ if $2^k$s places of $A$ and $B$ are both $1$, and $0$ otherwise.

Constraints

• $1 \leq K \leq 5 \times 10^4$
• $0 \leq N \leq 10^{18}$
• $N$ and $K$ are integers.

Input

The input is given from Standard Input in the following format:

$K$ $N$

Output

Print the answer.

Sample Input 1

2 6

Sample Output 1

21

$a_0$ and succeeding terms are $1, 1, 2, 3, 5, 8, 13, 21, \dots$. Four non-negative integers, $0, 2, 4$, and $6$, satisfy $6 \text{ AND } m = m$, so the answer is $1 + 2 + 5 + 13 = 21$.

Sample Input 2

2 8

Sample Output 2

35

Sample Input 3

1 123456789

Sample Output 3

65536

Sample Input 4

300 20230429

Sample Output 4

125461938

Sample Input 5

42923 999999999558876113

Sample Output 5

300300300

update @ 2024/3/10 08:25:15