問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) と整数 K が与えられます．

あなたは A のコピーを K 個並べて連結し，長さ NK の整数列 x=(x_1,x_2,\cdots,x_{NK}) を得ました．

あなたはこれから次の操作をちょうど 1 回行います．

• x の（連続とは限らない）（空でもよい）部分列を選び，その要素を逆順に並べ替える． より正確に述べれば，index の列 1 \leq i_1<i_2<\cdots<i_s \leq NK (列の長さ s も任意) を選び，各 1 \leq j \leq s に対して x_{i_j} の値を x_{i_{s-j+1}} で置き換える． この置き換えはすべて同時に行われる．

操作後の x としてありうる数列の個数を 998244353 で割ったあまりを求めてください．

制約

• 1 \leq N \leq 300
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq N
• 入力される値はすべて整数

入力例 1

2 2
1 2

出力例 1

6

この例では，x=(1,2,1,2) です． 操作後の x としてあり得る数列は以下の 6 通りです．

• (1,2,1,2) : s=1, (i_1)=(1) とすればよい．
• (2,1,1,2) : s=2, (i_1,i_2)=(1,2) とすればよい．
• (1,1,2,2) : s=2, (i_1,i_2)=(2,3) とすればよい．
• (1,2,2,1) : s=2, (i_1,i_2)=(3,4) とすればよい．
• (2,2,1,1) : s=2, (i_1,i_2)=(1,4) とすればよい．
• (2,1,2,1) : s=4, (i_1,i_2,i_3,i_4)=(1,2,3,4) とすればよい．

入力例 2

3 2
3 3 3

出力例 2

1

入力例 3

5 3
1 2 3 4 5

出力例 3

9216

入力例 4

30 1000000000000
8 3 8 10 1 5 3 1 6 4 3 6 2 6 6 9 5 5 8 3 3 4 10 2 3 2 8 10 8 1

出力例 4

401626004