問題文

正整数列 $A=(A_1,\ldots,A_N)$ と正整数 $K$ が与えられます。

小星さんは次のようなゲームを行います。はじめスコアは $1$ とし、$i=1,2,\ldots,N$ に対して座標 $i$ に石を $A_i$ 個置きます。

$i=N,N-1,\ldots,1$ の順に次の操作を行います。

• 座標 $i$ にあるすべての石を座標 $0,1,\ldots,i-1$ のいずれかに動かす。座標 $j$ に動かす石の個数を $c_j$ とするとき、スコアに $f(c_0)f(c_1)\cdots f(c_{i-1})$ をかける。ここで $$ f(m)=\begin{cases} K^m-K^{m-1} & (m>0) \\ 1 & (m=0) \end{cases} $$ である。

可能な操作方法すべてについての最終的なスコアの総和を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1\le T\le 10^5$
• $1\le N\le 2\times 10^5$
• $1\le A_i\lt 998244353$
• $2\le K\lt 998244353$
• 入力はすべて整数
• $1$ つの入力に含まれるテストケースについて、$N$ の総和は $2\times 10^5$ 以下

入力

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

各ケースは以下の形式で与えられます。

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

1
2 10
1 2

89100

2
1 2
3
3 3281572
842184 12484 58238890

4
724046312