{"raw_statement":[{"iden":"statement","content":"Doctor Sunset is doing a survey about global warming. He selected two cities $A$ and $B$, and has gathered the average air temperature of these two cities throughout passed $n$ days. On the $i$-th day, the average air temperature of $A$ was $a_i$ while the average air temperature of $B$ was $b_i$.\n\nDoctor Sunset drew a key graph using the temperature data. From his observation, there are several facts about the data:\n\nUnfortunately, Doctor Sunset erased all the data of city $B$ by mistake just now. But he can recover the array $b$ by the facts described above. Please write a program to help Sunset count the number of possible arrays that can be $b$.\n\nThe first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.\n\nIn each test case, there is one integer $n (1 <= n <= 2 times 10^5)$ in the first line, denoting the number of days.\n\nIn the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= n)$, denoting the average air temperature of city $A$. The input is always valid, so you can assume $a_1 <= a_2 <= a_3 <= \\\\dots <= a_n$.\n\nIt is guaranteed that $sum n <= 5 times 10^5$.\n\nFor each test case, print a single line containing an integer, denoting the number of possible arrays that can be $b$. As the answer can be very large, output it modulo $998244353$.\n\n"},{"iden":"input","content":"The first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 2 times 10^5)$ in the first line, denoting the number of days.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= n)$, denoting the average air temperature of city $A$. The input is always valid, so you can assume $a_1 <= a_2 <= a_3 <= \\\\dots <= a_n$.It is guaranteed that $sum n <= 5 times 10^5$."},{"iden":"output","content":"For each test case, print a single line containing an integer, denoting the number of possible arrays that can be $b$. As the answer can be very large, output it modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 50 $.  \nLet $ S_n $ be the set of all permutations of $ \\{1, 2, \\dots, n\\} $.  \nA permutation $ \\pi \\in S_n $ is *almost sorted* if $ \\mathrm{LIS}(\\pi) \\geq n - 1 $, where $ \\mathrm{LIS}(\\pi) $ denotes the length of the longest increasing subsequence of $ \\pi $.  \n\nLet $ B^k(\\pi) $ denote the permutation obtained after applying $ k $ passes of bubble sort to $ \\pi $.\n\n**Constraints**  \n1. $ 1 \\leq n, k \\leq 50 $  \n2. $ q $ is a prime number with $ 10^8 \\leq q \\leq 10^9 $  \n3. Number of test cases $ T \\leq 5000 $\n\n**Objective**  \nFor each test case, compute:  \n$$\n\\left| \\left\\{ \\pi \\in S_n \\mid \\mathrm{LIS}(B^k(\\pi)) \\geq n - 1 \\right\\} \\right| \\mod q\n$$","simple_statement":"Count permutations of 1 to n that, after k passes of bubble sort, become almost sorted (LIS ≥ n-1). Output answer mod q.","has_page_source":false}