F1. Appending Permutations (Easy Version)
combinatorics; dp
This is the easy version of the problem. The difference between the versions is that in this version, \(n \leq 100\). You can hack only if you solved all versions of this problem. You are given an initially empty array \(a\). You may perform the following operation any number of times: Choose an integer \(s \ge 1\) and append a cyclic shift of the array \([1, 2, \ldots, s]\) to the end of \(a\). Formally, select integers \(s\) and \(r\) such that \(1 \le r \le s\), and append the array $$$\( [r, r+1, \ldots, s, 1, 2, \ldots, r-1] \)\( to the end of \)a\(. You are also given an integer \)n\( and \)m\( restrictions of the form \)a_i \ne x\(. That is, for each of the \)m\( restrictions, the value at position \)i\( in the final array must not be equal to \)x\(.Your task is to count the number of distinct arrays of length exactly \)n\( that can be constructed using the allowed operation and satisfy all of the given restrictions. Two arrays are considered different if they differ at any position from \)1\( to \)n\(.Print the answer modulo \)998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 100\)). The description of the test cases follows. The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq n \leq 100, 0 \leq m \leq \min(5000, n^2)\)) — denoting the length of the array \(a\) and the number of restrictions.The following \(m\) lines each contain two integers \(i\) and \(x\) (\(1 \leq i,x \leq n\)), indicating that \(a_i\neq x\) is a requirement of the final array. It is guaranteed that no limitation is given more than once.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(100\), and the sum of \(m\) over all test cases does not exceed \(5000\).
For each test case, output the number of arrays modulo \(998\,244\,353\).
In the first test case, there are \(7\) total attainable arrays: \([1,2,3], [2,3,1], [3,1,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1]\).In the second test case, none of the above \(7\) are valid because no element is allowed to be \(1\), and all of the arrays have at least one \(1\).In the third case, only \([2,3,1]\) is counted.