{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \\dots, A_{M})$.\nHere, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive.\nFind the number, modulo $998244353$, of permutations $P$ of $(0, 1, \\dots, N-1)$ that satisfy the following condition.\n\n*   After initializing a sequence $B = (B_{1}, B_{2}, \\dots, B_{N})$ to $P$, it is possible to make $B = A$ by repeating the following operation some number of times:\n    *   Choose $l$ and $r$ such that $1 \\leq l \\leq r \\leq |B|$, and if $\\mathrm{mex}({B_{l}, B_{l+1}, \\dots, B_{r}})$ is contained in $B$, remove it from $B$.\n\nWhat is $\\mathrm{mex}(X)$? For a finite set $X$ of non-negative integers, $\\mathrm{mex}(X)$ is defined as the smallest non-negative integer that is not in $X$."},{"iden":"constraints","content":"*   $1 \\leq M \\leq N \\leq 500$\n*   $0 \\leq A_{i} < N$\n*   All elements of $A$ are distinct.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_{1}$ $A_{2}$ $\\cdots$ $A_{M}$"},{"iden":"sample input 1","content":"4 2\n1 3"},{"iden":"sample output 1","content":"8\n\nAfter initializing $B = (2, 1, 0, 3)$, it is possible to make $B = A$ using the following steps:\n\n*   Choose $(l, r) = (2, 4)$, remove $\\mathrm{mex}({1, 0, 3}) = 2$ from $B$, making $B = (1, 0, 3)$.\n*   Choose $(l, r) = (3, 3)$, remove $\\mathrm{mex}({3}) = 0$ from $B$, making $B = (1, 3)$.\n\nThus, $P = (2, 1, 0, 3)$ satisfies the condition.\nThere are eight permutations $P$ that satisfy the condition, including the above, so print $8$."},{"iden":"sample input 2","content":"4 4\n0 3 2 1"},{"iden":"sample output 2","content":"1\n\nOnly $P = (0, 3, 2, 1)$ satisfies the condition."},{"iden":"sample input 3","content":"16 7\n9 2 4 0 1 6 7"},{"iden":"sample output 3","content":"3520"},{"iden":"sample input 4","content":"92 4\n1 67 16 7"},{"iden":"sample output 4","content":"726870122\n\nFind the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}