CF2124F1.Appending Permutations (Easy Version)

这是该问题的简单版本。不同版本的区别在于本版本中 $n \leq 100$。只有在你解决了所有版本后才能进行 hack。

你有一个初始为空的数组 $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$ 和 $m$ 个限制条件，每个限制条件形如 $a_i \ne x$。也就是说，对于每个限制条件，最终数组的第 $i$ 个位置上的值不能等于 $x$。

你的任务是统计，使用允许的操作并满足所有限制条件后，能构造出多少个长度恰好为 $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$），表示最终数组的第 $i$ 个位置不能等于 $x$。保证没有重复的限制条件。

保证所有测试用例中 $n$ 的总和不超过 $100$，所有测试用例中 $m$ 的总和不超过 $5000$。

对于每个测试用例，输出满足条件的数组数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，一共可以得到 $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]$ 被计入。

由 ChatGPT 4.1 翻译