俾你一個 $\{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]$。
呢啲係唯一可以達到嘅數組。