{"problem":{"name":"K-Medians Clustering","description":{"content":"You are given positive integers $N, M, K$, and a sequence of $K$ positive integers $c=(c_1, c_2, \\dots, c_K)$. A **multiset** $S$ consisting of $N$ positive integers less than or equal to $M$ is calle","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"1202Contest_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N \\ M \\ K$\n$c_1 \\ c_2 \\ \\dots \\ c_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"1202Contest_f","tags":[],"sample_group":[["8 5 3\n4 1 5","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$"],["10000000 2 2\n1 2","9999999"],["30 10 5\n3 1 4 1 5","38446044"]],"created_at":"2026-03-03 11:01:13"}}