And DNA
给定两个整数 N,M,请计算满足以下条件的长度为 N 的整数序列 A=(A1,A2,…,AN) 的数量:
- 每个元素满足 0≤Ai≤M。
- 对于所有 1≤i≤N,有
Ai+(Ai−1&Ai+1)=M.
其中 A0=AN、AN+1=A1,即序列首尾相接;& 表示按位与运算。等式中的加号表示普通整数加法。
答案对 998244353 取模。序列的各个位置有固定编号,循环移位后得到的不同序列分别计数。
输入格式
一行两个整数 N,M,满足 3≤N≤109、0≤M≤109。
输出格式
输出一个整数,表示符合条件的序列数量对 998244353 取模的结果。
样例 1
输入:
3 2
输出:
4
四个符合条件的序列分别为 (0,2,2)、(2,0,2)、(2,2,0) 和 (1,1,1)。
样例 2
输入:
3 0
输出:
1
唯一符合条件的序列为 (0,0,0)。
样例 3
输入:
100 100
输出:
343406454