問題文

$N$ 個の歯車があり，$i$ 個目の歯車には $A_i$ 個の歯がついています．$i=1,2,\dots,N-1$ について，歯車 $i$ と歯車 $i+1$ は噛み合っており，歯車 $i$ が歯 1 個分回転すると，歯車 $i+1$ も連動して歯 1 個分回転します．

これから，$M$ 色を使ってそれぞれの歯車のそれぞれの歯を塗ります．回転によって一致する色の塗り方を同一視するとき，色の塗り方は何通りありますか．$998244353$ で割った余りを求めてください．

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

• $2 \leq N \leq 1000$
• $1 \leq M \lt 998244353$
• $3 \leq A_i \lt 998244353$
• $\mathrm{lcm}(A_1,A_2,\dots,A_N) \lt 998244353$
• 入力はすべて整数

出力

答えを $998244353$ で割った余りを出力してください． 最後に改行してください。

サンプル

2 2
3 3

24

2 3
3 4

264

3 4
3 5 7

11701248

4 100
10 1000 100000 100000000

827082837