题目描述

以下の条件を満たす項数 $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$ で割った余り」が異なる

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$

输出格式

答えを出力せよ。

题目大意

计算有多少个 $N$ 个元素的数组 $A = (a_1,...,a_N)$ 满足以下条件，并且将结果对 $998244353$ 取模。

• $0 \le a_1 \le a_2 \le...\le a_N \le M$
• 对于每一个 $i = 1,2,..,N-1$，满足 $a_i$ 和 $a_{i+1}$ 对 $3$ 取模的余数不同。

$2 \le N \le 10^7,1 \le M \le 10^7.$

3 4

8

276 10000000

909213205

提示

制約

• $2\ \leq\ N\ \leq\ 10^7$
• $1\ \leq\ M\ \leq\ 10^7$
• 入力はすべて整数

Sample Explanation 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)$

Sample Explanation 2

個数を $998244353$ で割った余りを求めてください。