{"problem":{"name":"Modifications","description":{"content":"You have an integer sequence $a=(a_1,a_2,\\cdots,a_N)$ of length $N$. All elements are initially $0$. You are given an integer $C$ and $M$ intervals $([L_1,R_1],[L_2,R_2],\\cdots,[L_M,R_M])$. You will c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc067_b"},"statements":[{"statement_type":"Markdown","content":"You have an integer sequence $a=(a_1,a_2,\\cdots,a_N)$ of length $N$. All elements are initially $0$.\nYou are given an integer $C$ and $M$ intervals $([L_1,R_1],[L_2,R_2],\\cdots,[L_M,R_M])$.\nYou will choose a permutation $p$ of $(1,2,\\cdots,M)$ and an integer sequence $w=(w_1,w_2,\\cdots,w_M)$ of length $M$. Here, $1\\le w_i\\le C$ must hold.\nThen, you will do $M$ modifications. The $i$\\-th modification is the following:\n\n*   Change $a_{L_{p_i}}, \\cdots, a_{R_{p_i}}$ to $w_i$.\n\nIt is guaranteed that every position in $a$ is covered by at least one interval.\nFind the number of achievable $a$ after all modifications. Print the answer modulo $998244353$.\n\n## Constraints\n\n*   $1\\le N\\le 100$\n*   $1\\le M\\le\\dfrac{N(N+1)}{2}$\n*   $1\\le C<998244353$\n*   $1 \\le L_i \\le R_i \\le N$\n*   $(L_i,R_i) \\neq (L_j,R_j)$ ($i \\neq j$)\n*   Every position in $a$ is covered by at least one interval.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $C$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_M$ $R_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc067_b","tags":[],"sample_group":[["5 5 2\n1 3\n2 2\n3 3\n1 5\n3 5","16\n\nThere are $16$ sequences that can be achieved. For example, you can achieve $a=(2,1,1,1,1)$ in the following manner:\n\n*   Choose $p=(4,1,2,3,5)$ and $w=(1,2,1,2,1)$\n*   The $1$\\-st operation changes $a$ into $(1,1,1,1,1)$\n*   The $2$\\-nd operation changes $a$ into $(2,2,2,1,1)$\n*   The $3$\\-rd operation changes $a$ into $(2,1,2,1,1)$\n*   The $4$\\-th operation changes $a$ into $(2,1,2,1,1)$\n*   The $5$\\-th operation changes $a$ into $(2,1,1,1,1)$"],["20 30 20\n1 14\n1 7\n1 16\n3 13\n1 17\n4 8\n2 11\n4 12\n9 14\n3 15\n11 19\n1 13\n4 15\n8 19\n3 17\n15 18\n10 18\n1 18\n17 19\n16 20\n1 8\n8 15\n13 17\n1 19\n13 19\n1 20\n6 13\n10 12\n11 20\n17 18","258066445"]],"created_at":"2026-03-03 11:01:14"}}