AT_arc223_f [ARC223F] Zonal Score Maximization

長さ $ 2 $ 以上の正整数列のスコアをその数列の最大値と最小値の和で定義します。 長さ $ 2 $ 以上の正整数列 $ A $ に対して、 $ A $ を長さ $ 2 $ 以上であるような $ 1 $ つ以上の連続部分列に分割したときに各連続部分列のスコアの総和としてあり得る値の最大値を $ f(A) $ とします。 より形式的には、ある正整数 $ K $ に対して長さが $ 2 $ 以上であるような $ K $ 個の正整数列 $ B_1,B_2,\dots,B_K $ をこの順に連結させると $ A $ と同じ数列になるときに $ \sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right) $ としてあり得る値の最大値を $ f(A) $ とします。 各要素が $ 1 $ 以上 $ N $ 以下の整数か $ -1 $ であるような長さ $ N $ の整数列 $ Q $ と、正整数 $ X $ が与えられます。 以下の条件をすべて満たすような $ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ の総数を $ 998244353 $ で割った余りを求めてください。 - $ i=1,2,\dots,N $ について、 $ Q_i \neq -1 $ ならば $ P_i=Q_i $ - $ f(P)=X $ $ 1 $ つの入力につき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。 > $ N $ $ X $ $ Q_1 $ $ Q_2 $ $ \dots $ $ Q_N $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ 1 $ つ目の条件を満たすような $ P $ は $ (2,1,3),(2,3,1) $ の $ 2 $ つです。 どちらの場合でも、 $ P $ を長さ $ 2 $ 以上であるような連続部分列に分割する方法は、 $ P $ 自身のみからなる $ 1 $ つの連続部分列に分割するという方法しかありません。その場合のスコアの総和は $ 3+1=4 $ なので、 $ f(P)=4 $ となります。 $ 2 $ つ目のテストケースでは、 $ P=(1,3,4,2) $ を $ (1,3) $ と $ (4,2) $ に分割するとスコアの総和は $ 10 $ となり、これ以上は大きくできないため、 $ f(P)=10 $ となります。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 10^5 $ - $ 1 \leq X \leq 10^{18} $ - $ Q_i=-1 $ または $ 1 \leq Q_i \leq N $ - $ Q_i \neq -1 $ かつ $ Q_j \neq -1 $ ならば $ Q_i \neq Q_j\;(i \neq j) $ - すべてのテストケースにおける $ N $ の総和は $ 10^5 $ 以下 - 入力される値はすべて整数