#P18198. And DNA

And DNA

And DNA

给定两个整数 N,MN,M,请计算满足以下条件的长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) 的数量:

  • 每个元素满足 0≤Ai≤M0\le A_i\le M。
  • 对于所有 1≤i≤N1\le i\le N,有
Ai+(Ai−1&Ai+1)=M.A_i+(A_{i-1}\mathbin{\&}A_{i+1})=M.

其中 A0=ANA_0=A_N、AN+1=A1A_{N+1}=A_1,即序列首尾相接;&\& 表示按位与运算。等式中的加号表示普通整数加法。

答案对 998244353998244353 取模。序列的各个位置有固定编号,循环移位后得到的不同序列分别计数。

输入格式

一行两个整数 N,MN,M,满足 3≤N≤1093\le N\le10^9、0≤M≤1090\le M\le10^9。

输出格式

输出一个整数,表示符合条件的序列数量对 998244353998244353 取模的结果。

样例 1

输入:

3 2

输出:

4

四个符合条件的序列分别为 (0,2,2)(0,2,2)、(2,0,2)(2,0,2)、(2,2,0)(2,2,0) 和 (1,1,1)(1,1,1)。

样例 2

输入:

3 0

输出:

1

唯一符合条件的序列为 (0,0,0)(0,0,0)。

样例 3

输入:

100 100

输出:

343406454