这是问题的简单版本。版本之间的差异在于,在此版本中,$$$n \leq 100$$$。只有解决了该问题的所有版本,您才能破解。
给你一个最初为空的数组$$$a$$$。您可以多次执行以下操作:
- 选择一个整数 $$$s \ge 1$$$ 并将数组 $$$[1, 2, \ldots, s]$$$ 的循环移位附加到 $$$a$$$ 的末尾。形式上,选择整数 $$$s$$$ 和 $$$r$$$ 使得 $$$1 \le r \le s$$$,并附加数组
$$[r, r+1, \ldots, s, 1, 2, \ldots, r-1]$$
到 $$$a$$$ 的末尾。
您的任务是计算长度恰好为 $$$n$$$ 的不同数组的数量,这些数组可以使用允许的操作构造并满足所有给定的限制。如果两个数组在 $$$1$$$ 到 $$$n$$$ 之间的任何位置不同,则认为它们不同。
打印以 $$$998\,244\,353$$$ 为模的答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 100, 0 \leq m \leq \min(5000, n^2)$$$) - 表示数组 $$$a$$$ 的长度和限制数量。
接下来的 $$$m$$$ 行每行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i,x \leq n$$$),表明 $$$a_i\neq x$$$ 是最终数组的要求。保证不会多次给出限制。
保证所有测试用例的$$$n$$$总和不超过$$$100$$$,所有测试用例的$$$m$$$总和不超过$$$5000$$$。
输出
对于每个测试用例,输出以 $$$998\,244\,353$$$ 为模的数组数量。
示例
输入复制
73 03 31 12 13 13 21 12 16 22 34 22 31 22 21 14 32 23 24 23 22 33 3
输出复制
7 0 1 65 0 4 5
输入复制
1100 169 69
输出复制
381055417
注意
在第一个测试用例中,总共可获得 $$$7$$$ 数组:$$$[1,2,3]、[2,3,1]、[3,1,2]、[1,1,2]、[1,2,1]、[2,1,1]、[1,1,1]$$$。
在第二个测试用例中,上述 $$$7$$$ 均无效,因为不允许任何元素为 $$$1$$$,并且所有数组都至少有一个 $$$1$$$。
在第三种情况下,仅计算$$$[2,3,1]$$$。