AT_arc219_b [ARC219B] Reverse Permutation

You are given an integer $ N $ and a permutation $ P=(P_1,P_2,\ldots,P_N) $ of $ (1,2,\ldots,N) $ . For a permutation $ Q=(Q_1,Q_2,\ldots,Q_N) $ of $ (1,2,\ldots,N) $ , let $ Q'=(Q_1',Q_2',\ldots,Q_N') $ be the lexicographically smallest permutation obtainable by performing the following operation exactly once: - Choose a pair of integers $ (l,r) $ satisfying $ 1\le l\le r\le N $ , and reverse $ Q_l,Q_{l+1},\ldots,Q_r $ . More precisely, replace $ Q $ with $ (Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N) $ . Find the number, modulo $ 998244353 $ , of permutations $ Q $ of $ (1,2,\ldots,N) $ such that $ Q'=P $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. For example, when $ Q=(2,3,1) $ , choosing $ (l,r)=(1,3) $ gives $ (1,3,2) $ . No permutation lexicographically smaller than $ (1,3,2) $ can be obtained, so we have $ Q'=(1,3,2) $ . Thus, $ Q=(2,3,1) $ satisfies $ Q'=P $ . There are two permutations $ Q $ such that $ Q'=P $ : $ Q=(2,3,1),(3,1,2) $ . ### Constraints - $ 1\le T $ - $ 1\le N\le 5\times 10^5 $ - $ P $ is a permutation of $ (1,2,\ldots,N) $ . - The sum of $ N $ over all test cases is at most $ 5\times 10^5 $ . - All input values are integers.