導入

もう一度, ゼロからやり直さない?

問題文

Make it Zero!

長さ $N$ の整数列 $B=(B_1, \dots, B_N)$ が与えられる. 各項は $0$ 以上 $M$ 未満の整数である. また, $\displaystyle \sum_{i=1}^N B_i$ は $M$ の倍数であることが保証されている.

ここで, 全ての項が $0$ である非空整数列を ゼロ列 ということにする.

以下の操作を $0$ 回以上繰り返して行うことにより, $B$ を ゼロ列 にする.

• 操作: $B$ にある連続する $2$ つの整数を選び, 削除する. そして, その削除した $2$ つの整数を $x,y$ としたとき, $(x+y)$ を $M$ で割った余りを元あった場所に挿入する.

$B$ を ゼロ列 にするためには, 最低何回の操作が必要か?

なお, この問題の制約下では, 操作を $0$ 回以上繰り返すことで, $B$ を ゼロ列 にすることが可能であることが証明できる.

長さ $N$ の整数列 $X=(X_1, \dots, X_N)$ が与えられる. $X$ の各項は $0$ 以上 $M$ 未満の整数または $-1$ である.

以下の $3$ 個の条件を満たす長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ において, そのような $A$ 全てに対する Make it Zero! の解の総和を $998244353$ で割った余りを求めよ.

• $i=1,2, \dots, N$ に対して, $0 \leq A_i \lt M$ である.
• $i=1,2, \dots, N$ に対して, $X_i \neq -1$ ならば, $A_i=X_i$ である.
• $\displaystyle \sum_{i=1}^N A_i$ は $M$ の倍数である.

ただし, このような $A$ が存在しない場合, 解の総和は $0$ であるとする.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 10^5$
• 各テストケースに対する制約
  • $1 \leq N \leq 2 \times 10^5$.
  • $1 \leq M \leq 10^9$.
  • $X_i$ は $0$ 以上 $M$ 未満の整数または $-1$ である. $\quad (1 \leq i \leq N)$.
• テストファイルに対する制約
  • $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^5$ 以下である.
• 入力は全て整数である.

入力

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

$N$ $M$
$X_1$ $X_2$ $\cdots$ $X_N$

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には第 $t$ テストケースに対する解答を整数として出力せよ.

最後に改行を忘れないこと.

サンプル

4
3 10
4 -1 7
5 100
10 20 30 40 50
6 123456789
0 0 0 0 0 0
6 20230628
-1 -1 -1 -1 -1 -1

2
0
0
324811269