給你一個 $\{1, 2, \dots, N\}$ 的排列 $P$。
也就是說,$P$ 是一個長度為 $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$ 開始。
每次此類操作都會使 $P$ 的長度減少 $2$。特別地,如果 $P$ 的長度為 $1$ 或 $2$,則無法進行此操作。
求從 $P$ 開始,透過執行零次或多次該操作可以達到的不同陣列的數量。
由於該值可能很大,你只需要求出其對 $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$ 執行零次或多次操作可以達到的不同陣列的數量,對 $998\,244\,353$ 取模。
範例
輸入範例 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:無法進行任何操作。
測試用例 2:有兩種可能性:
- 不進行任何操作。最終陣列為 $[2, 1, 3]$。
- 對 $i = 2$ 進行一次操作。最終陣列為 $[3]$。
這些是唯一可達的陣列。