{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N, M, K$, and a sequence of $K$ positive integers $c=(c_1, c_2, \\dots, c_K)$.\nA **multiset** $S$ consisting of $N$ positive integers less than or equal to $M$ is called _good_, if there exists at least one sequence of $K$ multisets $(S_1, S_2, \\dots, S_K)$ satisfying the following conditions.\n\n*   None of $S_1, S_2, \\dots, S_K$ is empty.\n*   The median of $S_i$ equals to $c_i$, for all $i=1, 2, \\dots, K$.\n*   $S_1, S_2, \\dots, S_K$ have exactly $N$ elements in total. A multiset consisting of those $N$ elements coincides with $S$.\n\nNote that we define the median of a multiset $T$ with $n\\ (\\geq 1)$ elements as the $\\lceil n / 2 \\rceil$\\-th element of $T$ in ascending order. For example, the median of $T=\\lbrace 1, 2, 3, 4 \\rbrace$ is $2$, and that of $T=\\lbrace 1, 3, 5, 7, 7 \\rbrace$ is $5$.\nFind the number of good multisets modulo $998244353$."},{"iden":"constraints","content":"*   $1 \\leq N, M \\leq 10^7$\n*   $1 \\leq K \\leq \\min(2 \\times 10^5, N)$\n*   $1 \\leq c_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$N \\ M \\ K$\n$c_1 \\ c_2 \\ \\dots \\ c_K$"},{"iden":"sample input 1","content":"8 5 3\n4 1 5"},{"iden":"sample output 1","content":"105\n\nFor example, $S=\\lbrace 1,1,1,2,3,4,5,5 \\rbrace$ is a good multiset because there exists $(S_1, S_2, S_3)$ satisfying the conditions as follows.\n\n*   $S_1 = \\lbrace 1, \\mathbf{4}, 5 \\rbrace$\n*   $S_2 = \\lbrace 1, \\mathbf{1}, 2, 3 \\rbrace$\n*   $S_3 = \\lbrace \\mathbf{5} \\rbrace$"},{"iden":"sample input 2","content":"10000000 2 2\n1 2"},{"iden":"sample output 2","content":"9999999"},{"iden":"sample input 3","content":"30 10 5\n3 1 4 1 5"},{"iden":"sample output 3","content":"38446044"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}