{"problem":{"name":"Cigar Box","description":{"content":"We applied the following operation $m$ times on the sequence $(1,2,\\dots,n)$, and it resulted in $(a_1,\\dots ,a_n)$. *   Erase one element. Then, add the erased element to the beginning or end of the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc112_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $2\\le n \\le 3000$\n*   $1\\le m \\le 3000$\n*   $a_1,\\dots ,a_n$ is a permutation of $1,\\dots,n$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$ $m$\n$a_1$ $\\dots$ $a_n$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc112_e","tags":[],"sample_group":[["5 2\n1 2 4 5 3","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)$."],["2 16\n1 2","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$."],["10 3000\n3 7 10 1 9 5 4 8 6 2","129989699"]],"created_at":"2026-03-03 11:01:14"}}