← 返回题目列表

AtCoder · tupc2023_e

E. 和 DNA

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

配点 : 100 点

問題文

0 以上 M 由小于或等于的非负整数组成的长度 在 N 序列 使用 A=(A_1,A_2,\dots,A_N) 中,计算满足以下条件的项目数。 998244353 请求出除以后的余数。

  • 全部 i=1,2,\dots,N , A_i + (A_{i-1} \& A_{i+1})=M 。然而, A_0 \coloneqq A_N,A_{N+1} \coloneqq A_1 和 \& 是按位与。

制約

  • 3 \leq N \leq 10^9
  • 0 \leq M \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M

出力

打印答案。 来自


入力例 1

3 2

出力例 1

4

满足条件 A 是 您也可以写 (0,2,2), (2,0,2), (2,2,0), (1,1,1) 可以得到第 4 一。 请注意,无法创建


入力例 2

3 0

出力例 2

1

满足条件 A 是 您也可以写 (0,0,0) 可以得到第 1 一。 请注意,无法创建


入力例 3

100 100

出力例 3

343406454

998244353 请求出除以后的余数。