{"raw_statement":[{"iden":"statement","content":"有一个长度为 $n$，值域为 $[1,c]$ 的正整数序列 $a$。给定 $m$ 个区间 $[l_i,r_i]$，设长度为 $m$ 的序列 $b$ 满足 $\\forall i\\in [1,m],b_i=\\min\\limits_{j=l_i}^{r_i}\\{a_j\\}$。求出 $a$ 在范围内任意取的情况下共能得到多少种不同的 $b$。答案对 $998244353$ 取模。"},{"iden":"input","content":"第一行，三个数，依次表示 $n,m,c$。\n\n接下来 $m$ 行，每行两个数 $l_i,r_i$ 表示一个给定的区间。"},{"iden":"output","content":"共一行，一个数，表示答案。"},{"iden":"note","content":"对于 $100\\%$ 的数据，$1\\le n\\le 100,1\\le m\\le\\dfrac{n(n+1)}{2},1\\le c<998244353,\\forall i\\in [1,m],1\\le l_i\\le r_i\\le n$。保证给定的 $m$ 个区间两两不同。\n\n$\\operatorname{Subtask}1(5\\%):n,c\\le 5$。\n\n$\\operatorname{Subtask}2(10\\%):c\\le 100$，且对于任意两个有交点的区间一定存在其中一个包含另一个。\n\n$\\operatorname{Subtask}3(15\\%):m\\le 18,c=2$。\n\n$\\operatorname{Subtask}4(20\\%):c=2$。\n\n$\\operatorname{Subtask}5(15\\%):n,c\\le 40$。\n\n$\\operatorname{Subtask}6(15\\%):c\\le 100$。\n\n$\\operatorname{Subtask}7(20\\%):$ 无特殊限制。\n\n#### 样例说明 1\n\n当 $a=(1,1,1)$ 时，$b=(1,1)$。\n\n当 $a=(1,1,2)$ 时，$b=(1,1)$。\n\n当 $a=(1,2,1)$ 时，$b=(1,1)$。\n\n当 $a=(1,2,2)$ 时，$b=(1,2)$。\n\n当 $a=(2,1,1)$ 时，$b=(1,1)$。\n\n当 $a=(2,1,2)$ 时，$b=(1,1)$。\n\n当 $a=(2,2,1)$ 时，$b=(2,1)$。\n\n当 $a=(2,2,2)$ 时，$b=(2,2)$。\n\n因此共能得到 $[1,1],[1,2],[2,1],[2,2]$ 这 $4$ 种不同的 $b$。"}],"translated_statement":null,"sample_group":[["3 2 2\n1 2\n2 3","4"],["10 11 2\n1 10\n2 2\n3 3\n5 5\n6 10\n6 7\n6 6\n7 7\n8 10\n8 9\n10 10","129"],["40 40 40\n31 34\n9 34\n4 25\n36 38\n8 29\n8 30\n6 26\n17 19\n6 23\n36 39\n11 39\n2 10\n32 37\n32 33\n33 35\n17 21\n8 35\n31 40\n11 25\n11 20\n8 37\n26 36\n22 34\n17 39\n28 38\n26 28\n11 12\n12 15\n12 37\n1 9\n11 23\n5 26\n8 11\n1 23\n12 32\n7 19\n22 28\n20 27\n8 40\n19 40","567581188"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}