分数: 600 点
问题陈述
查找整数序列的数量 N 条款, A=(a_1,a_2,\ldots,a_N),满足以下条件,模 998244353.
- 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M.
- 对于每个 i=1,2,\ldots,N-1,余数 a_i 除以 3 与以下情况下的余数不同 a_{i+1} 除以 3.
约束
- 2 \leq N \leq 10^7
- 1 \leq M \leq 10^7
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
3 4
示例输出 1
8
这是满足条件的八个序列。
- (0,1,2)
- (0,1,3)
- (0,2,3)
- (0,2,4)
- (1,2,3)
- (1,2,4)
- (1,3,4)
- (2,3,4)
示例输入 2
276 10000000
示例输出 2
909213205
一定要找到计数模数 998244353.