長さ $n$ の数列が与えられる。小鳴はこれからこの数列に対して $n-1$ 回の操作を行う。各操作では、隣接する2つの数を等確率でランダムに選択し、その2つの数を「左側の数から右側の数を引いた値」に置き換える。1回目の操作後、数列の長さは $n-1$ になり、もう一度操作を行うと長さは $n-2$ になる。これを繰り返す。

$n-1$ 回の操作を行った後に最後に残る1つの数の期待値を求めよ。答えが $p/q$ であるとき、$p \times q^{998244351} \pmod{998244353}$ を出力せよ。

本問には複数のテストケースが含まれる。

入力

入力は以下の形式で与えられる。

$T$ $n_1$ $a_{1,1} \ a_{1,2} \ \dots \ a_{1,n_1}$ $n_2$ $a_{2,1} \ a_{2,2} \ \dots \ a_{2,n_2}$ $\vdots$ $n_T$ $a_{T,1} \ a_{T,2} \ \dots \ a_{T,n_T}$

1行目にテストケースの数 $T$ が与えられる。 各テストケースの1行目には数列の長さ $n$ が与えられる。 2行目には数列の各要素 $a_i$ が与えられる。

出力

各テストケースについて、期待値を求めた結果を1行ずつ出力せよ。

入出力例

入出力例 1

2
2
2 1
3
3 2 1

1
1

注記

2番目のクエリについて、先に最初の2つの数を選択した場合、結果は $(3 - 2) - 1 = 0$ となる。先に後ろの2つの数を選択した場合、結果は $3 - (2 - 1) = 2$ となる。したがって、期待値は $2/2 = 1$ である。

入出力例 2

選手ディレクトリ内の aminusb/aminusb2.in および aminusb/aminusb2.ans を参照すること。

子タスク

制約

すべてのデータにおいて、$T = 5$、$1 \le n \le 10^5$、$0 \le a_i < 998244353$ を満たす。