F. Сортировка пузырьком
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы только что узнали алгоритм сортировки пузырьком, который способен сортировать массив в неубывающем порядке. Определим функцию $$$\text{sort}(a)$$$ следующим образом в псевдокоде:

function sort(array a):
    rounds := 0  // создаём счётчик раундов
    n := length of a
    while a is not non-decreasing:  // пока массив a не является неубывающим
        rounds := rounds + 1
        for i from 1 to n - 1:
            if a[i] > a[i + 1]:
                swap(a[i], a[i + 1])
    return rounds

Возвращаемое значение $$$\text{sort}(a)$$$ представляет собой количество раундов, необходимых для сортировки массива $$$a$$$ в неубывающем порядке с использованием сортировки пузырьком.

Вам дано целое число $$$n$$$, а также $$$m$$$ кортежей целых чисел $$$(k_i,l_i,r_i)$$$ ($$$1\le i\le m$$$). Подсчитайте количество перестановок$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, по модулю $$$998\,244\,353$$$, для которых выполняются следующие ограничения:

  • Для каждого $$$1\le i\le n$$$, пусть $$$b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$$$, тогда
  • Для каждого $$$1\le j\le m$$$, пусть $$$x$$$ — это количество индексов $$$y$$$ ($$$1\le y\le n$$$) таких, что $$$b_y\le k_j$$$, тогда выполняется $$$l_j\le x\le r_j$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2\leq n\leq 10^6$$$, $$$0\leq m\leq 1000$$$).

Затем следуют $$$m$$$ строк, $$$i$$$-я строка содержит три целых числа $$$k_i$$$, $$$l_i$$$ и $$$r_i$$$ ($$$0\le k_i\le n - 1$$$, $$$1\le l_i\le r_i\le n$$$) — ограничения.

Гарантируется, что сумма значений $$$m^2$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
6
4 3
0 1 1
1 3 3
2 4 4
3 2
0 3 3
1 2 3
4 3
1 2 2
2 3 4
0 1 2
5 3
1 1 4
3 5 5
4 5 5
10 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
1000000 0
Выходные данные
2
1
8
80
192600
373341033
Примечание

В первом наборе входных данных только перестановки $$$[3,1,4,2]$$$ и $$$[4,1,3,2]$$$ удовлетворяют условиям. Возьмём $$$[3,1,4,2]$$$ в качестве примера. Давайте вычислим массив $$$b$$$:

  • $$$\text{sort}([3])=0$$$;
  • $$$\text{sort}([3,1])=1$$$;
  • $$$\text{sort}([3,1,4])=1$$$;
  • $$$\text{sort}([3,1,4,2])=2$$$.

Таким образом, $$$b=[0,1,1,2]$$$. Легко показать, что он удовлетворяет всем ограничениям.

Во втором наборе входных данных только перестановка $$$[1,2,3]$$$ удовлетворяет ограничениям.

В третьем наборе входных данных следующие $$$8$$$ перестановок удовлетворяют ограничениям:

  • $$$[2,3,1,4]$$$;
  • $$$[2,4,1,3]$$$;
  • $$$[3,2,1,4]$$$;
  • $$$[3,4,1,2]$$$;
  • $$$[3,4,2,1]$$$;
  • $$$[4,2,1,3]$$$;
  • $$$[4,3,1,2]$$$;
  • $$$[4,3,2,1]$$$.