F1. Конкатенация перестановок (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$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$$$ и $$$m$$$ ограничений вида $$$a_i \ne x$$$. То есть, для каждого из $$$m$$$ ограничений значение на позиции $$$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$$$): в конечном массиве требуется $$$a_i\neq x$$$. Гарантируется, что ни одно ограничение не дано более одного раза.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$, а сумма $$$m$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите количество массивов по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
7
3 0
3 3
1 1
2 1
3 1
3 2
1 1
2 1
6 2
2 3
4 2
2 3
1 2
2 2
1 1
4 3
2 2
3 2
4 2
3 2
2 3
3 3
Выходные данные
7
0
1
65
0
4
5
Входные данные
1
100 1
69 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]$$$.