配点 : $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$

出力

答えを出力せよ。

3 4

8

以下の $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)$

276 10000000

909213205

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