{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $(X_1, X_2, \\dots, X_M)$ of length $M$ consisting of integers between $1$ and $M$, inclusive.\nFind the number, modulo $998244353$, of sequences $A = (A_1, A_2, \\dots, A_N)$ of length $N$ consisting of integers between $1$ and $M$, inclusive, that satisfy the following condition:\n\n*   For each $B = 1, 2, \\dots, M$, the value $X_B$ exists between any two different occurrences of $B$ in $A$ (including both ends).\n\nMore formally, for each $B = 1, 2, \\dots, M$, the following condition must hold:\n\n*   For every pair of integers $(l, r)$ such that $1 \\leq l < r \\leq N$ and $A_l = A_r = B$, there exists an integer $m$ ($l \\leq m \\leq r$) such that $A_m = X_B$."},{"iden":"constraints","content":"*   $1 \\leq M \\leq 10$\n*   $1 \\leq N \\leq 10^4$\n*   $1 \\leq X_i \\leq M$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$M$ $N$\n$X_1$ $X_2$ $\\cdots$ $X_M$"},{"iden":"sample input 1","content":"3 4\n2 1 2"},{"iden":"sample output 1","content":"14\n\nHere are examples of sequences $A$ that satisfy the condition:\n\n*   $(1, 3, 2, 3)$\n*   $(2, 1, 2, 1)$\n*   $(3, 2, 1, 3)$\n\nHere are non-examples:\n\n*   $(1, 3, 1, 3)$\n    *   There is no $X_3 = 2$ between the $3$s.\n*   $(2, 2, 1, 3)$\n    *   There is no $X_2 = 1$ between the $2$s."},{"iden":"sample input 2","content":"4 8\n1 2 3 4"},{"iden":"sample output 2","content":"65536\n\nAll sequences of length $8$ consisting of integers between $1$ and $4$ satisfy the condition.\nNote that when $X_B = B$, there is always a $B$ between two different occurrences of $B$."},{"iden":"sample input 3","content":"4 9\n2 3 4 1"},{"iden":"sample output 3","content":"628"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}