{"raw_statement":[{"iden":"problem statement","content":"We applied the following operation $m$ times on the sequence $(1,2,\\dots,n)$, and it resulted in $(a_1,\\dots ,a_n)$.\n\n*   Erase one element. Then, add the erased element to the beginning or end of the sequence.\n\nFind the number of possible sequences of the $m$ operations, modulo $998244353$.\nHere, two sequences of operations are considered the same when, in every operation, the same element is chosen and added to the same position."},{"iden":"constraints","content":"*   $2\\le n \\le 3000$\n*   $1\\le m \\le 3000$\n*   $a_1,\\dots ,a_n$ is a permutation of $1,\\dots,n$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$n$ $m$\n$a_1$ $\\dots$ $a_n$"},{"iden":"sample input 1","content":"5 2\n1 2 4 5 3"},{"iden":"sample output 1","content":"5\n\nThere are five possible sequences of operations, as follows:\n\n*   Erase $1$ and add it to the beginning, which results in $(1,2,3,4,5)$. Then, erase $3$ and add it to the end, which results in $(1,2,4,5,3)$.\n*   Erase $3$ and add it to the beginning, which results in $(3,1,2,4,5)$. Then, erase $3$ and add it to the end, which results in $(1,2,4,5,3)$.\n*   Erase $3$ and add it to the end, which results in $(1,2,4,5,3)$. Then, erase $1$ and add it to the beginning, which results in $(1,2,4,5,3)$.\n*   Erase $3$ and add it to the end, which results in $(1,2,4,5,3)$. Then, erase $3$ and add it to the end, which results in $(1,2,4,5,3)$.\n*   Erase $5$ and add it to the end, which results in $(1,2,3,4,5)$. Then, erase $3$ and add it to the end, which results in $(1,2,4,5,3)$."},{"iden":"sample input 2","content":"2 16\n1 2"},{"iden":"sample output 2","content":"150994942\n\nTwo of the four kinds of operations have no effect on the sequence, and the other two swap the two elements. From this fact, we can show that there are $4^m/2 = 2^{31} = 2147483648$ sequences of operations - half of all possible sequences - that we want to count. Thus, the answer is $2147483648$ modulo $998244353$, that is, $150994942$."},{"iden":"sample input 3","content":"10 3000\n3 7 10 1 9 5 4 8 6 2"},{"iden":"sample output 3","content":"129989699"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}