分数: 700 点
问题陈述
给你正整数 N 和 K。求模数 998244353,整数序列 \bigl(f(0), f(1), \ldots, f(2^N-1)\bigr) 满足以下所有条件:
- 0\leq f(x)\leq K 对于所有非负整数 x (0\leq x \leq 2^N-1).
- f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y) 对于所有非负整数 x 和 y (0\leq x, y \leq 2^N-1)
在这里, \mathrm{AND} 和 \mathrm{OR} 分别表示按位AND和OR。
约束
- 1\leq N\leq 3\times 10^5
- 1\leq K\leq 10^{18}
输入
输入由标准输入按以下格式给出:
N K
输出
打印数字,模数 998244353,满足条件的整数序列。
示例输入 1
2 1
示例输出 1
6
以下六个整数序列满足条件:
- (0,0,0,0)
- (0,1,0,1)
- (0,0,1,1)
- (1,0,1,0)
- (1,1,0,0)
- (1,1,1,1)
示例输入 2
2 2
示例输出 2
19
示例输入 3
100 123456789123456789
示例输出 3
34663745