{"problem":{"name":"Sliding Window Sort","description":{"content":"You are given positive integers $N$, $M$, and $K$. Consider the following operation on a sequence of positive integers $A = (A_0, \\ldots, A_{N-1})$. *   Do the following for $k=0, 1, \\ldots, K-1$ in ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc149_e"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $N$, $M$, and $K$. Consider the following operation on a sequence of positive integers $A = (A_0, \\ldots, A_{N-1})$.\n\n*   Do the following for $k=0, 1, \\ldots, K-1$ in this order.\n    *   Sort $A_{k\\bmod N}, A_{(k+1)\\bmod N}, \\ldots, A_{(k+M-1)\\bmod N}$ in ascending order. That is, replace $A_{(k+j)\\bmod N}$ with $x_j$ for each $0\\leq j < M$, where $(x_0, \\ldots, x_{M-1})$ is the result of sorting $A_{k\\bmod N}, A_{(k+1)\\bmod N}, \\ldots, A_{(k+M-1)\\bmod N}$ in ascending order.\n\nYou are given a permutation $B = (B_0, \\ldots, B_{N-1})$ of the integers from $1$ through $N$. Find the number of sequences $A$ of positive integers that will equal $B$ after performing the operation above, modulo $998244353$.\n\n## Constraints\n\n*   $2\\leq N\\leq 3\\times 10^5$\n*   $2\\leq M\\leq N$\n*   $1\\leq K\\leq 10^9$\n*   $1\\leq B_i\\leq N$\n*   $B_i\\neq B_j$ if $i\\neq j$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$B_0$ $\\ldots$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc149_e","tags":[],"sample_group":[["6 3 5\n6 4 2 3 1 5","18\n\nFor instance, $A = (4,1,5,6,2,3)$ satisfies the condition. On this $A$, the operation will proceed as follows.\n\n*   The action for $k=0$ changes $A$ to $(1,4,5,6,2,3)$.\n*   The action for $k=1$ changes $A$ to $(1,4,5,6,2,3)$.\n*   The action for $k=2$ changes $A$ to $(1,4,2,5,6,3)$.\n*   The action for $k=3$ changes $A$ to $(1,4,2,3,5,6)$.\n*   The action for $k=4$ changes $A$ to $(6,4,2,3,1,5)$, which equals $B$."],["6 3 5\n6 5 4 3 2 1","0\n\nNo sequence $A$ satisfies the condition."],["20 20 149\n13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12","401576539\n\nAll permutations of the integers from $1$ through $20$ satisfy the condition."]],"created_at":"2026-03-03 11:01:14"}}