Excuse

初投稿につき、問題文が分かりにくかったり、面白くなかったり、あるいはその他何かしらの不備があったりするかもしれません。ご指摘・ご助言等ございましたら作者のTwitter(X)やマシュマロにいただけると幸いです。

問題文

縦横 $N$ マスのグリッドがあります。左上隅のマスを $(0,0)$ とし、そこから下に $i$ マス、右に $j$ マス(ただし $0\leq i,j\leq N-1$ )進んだ地点にあるマスを $(i,j)$ と呼びます。 時刻 $t=0$ において $(0,0)$ にアメーバが $1$ 匹存在し、それ以外にアメーバは存在しません。これから、時刻 $t=1,2,3,......$ に、その時刻において存在するすべてのアメーバが、次のような規則に従って同時に、無視できる程度の時間で増殖します。

• 現在アメーバが存在するマスを $(i,j)$ とすると、アメーバは $4$ 匹に分裂し、その後 $(i+1\bmod N,j),(i-1\bmod N,j),(i,j+1\bmod N),(i,j-1\bmod N)$ の $4$ マスそれぞれに、分裂したアメーバが $1$ 匹ずつ移動する。言い換えれば、時刻 $t(t\geq 1)$ の分裂が終わった直後に $(i,j)$ に存在するアメーバの数は、その分裂の直前に $(i-1\bmod N,j),(i+1\bmod N,j),(i,j-1\bmod N),(i,j+1\bmod N)$ の $4$ マスに存在したアメーバの数の和に等しい。

非負整数 $T$ が与えられます。時刻 $t=T+0.5$ において $(0,0)$ に存在するアメーバの数を $998244353$ で割った余りを求めてください。

制約

• $3\leq N\leq 1000$
• $0\leq T\leq 2\times 10^6$

入力

入力は全て整数である。

N T

出力

答えを出力せよ。

サンプル

3 4

36

$N=3$ のとき、 $t=1.5,2.5,3.5,4.5$ の各時点において、各マスのアメーバの数は下図のようになります。よって、 $36$ を出力します。

t=1.5      t=2.5       t=3.5       t=4.5
 0 1 1      4 1 1       4 9 9       36 25 25
 1 0 0      1 2 2       9 6 6       25 30 30
 1 0 0      1 2 2       9 6 6       25 30 30

10 1

0

$t=1.5$ の時点で、$(0,0)$ にはアメーバは $1$ 匹も存在しません。

1000 0

1

100 100000

808960092

$998244353$ で割ったあまりを出力してください。