$\{1, 2, \dots, N\}$ の順列 $P$ が与えられます。
つまり、$P$ は $1$ から $N$ までの各整数をちょうど 1 回ずつ含む長さ $N$ の配列です。
これに対して以下の操作を行うことができます:
- インデックス $i$($1 < i < |P|$)を選ぶ。
- $P_i = \max(P_{i-1}, P_i, P_{i+1})$ と設定する。
- $P$ から $P_{i-1}$ と $P_{i+1}$ を削除する。残った要素は $1$ から始まるようにインデックスが振り直される。
このような操作を 1 回行うごとに、$P$ の長さは $2$ 減少します。特に、$P$ の長さが $1$ または $2$ の場合、この操作は適用できません。
$P$ から始めてこの操作を 0 回以上行うことで到達できる異なる配列の個数を求めてください。
この値は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを求めてください。
入力
入力は以下の形式で与えられます:
T N P_1 P_2 ... P_N ...
制約
- 入力値はすべて整数である。
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- すべての $i \ne j$ について $P_i \ne P_j$。
- すべてのテストケースにおける $N^2$ の総和は $5000^2$ を超えないことが保証される。
出力
各テストケースについて、$P$ に対して操作を 0 回以上行うことで到達できる異なる配列の個数を $998\,244\,353$ で割った余りを 1 つの整数として出力せよ。
入出力例
入力例 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
出力例 1
1 2 5 55 365
注記
テストケース 1: 操作を 1 回も行うことができません。
テストケース 2: 以下の 2 通りの可能性があります:
- 操作を行わない。最終的な配列は $[2, 1, 3]$ である。
- $i = 2$ として操作を 1 回行う。最終的な配列は $[3]$ である。
到達可能な配列はこれらのみです。