F. Жили и цветные строки
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

С первого дня рождения Жили, Джили каждый год дарит ему цветную нитку, и каждый год подарок отличается от всех предыдущих. В этом году Жили с удивлением обнаружил, что получил все возможные уникальные подарки!

Назовём цветную строку, удовлетворяющую следующим условиям, допустимой:

  1. Она состоит из $$$m$$$ типов символов, причем символов $$$i$$$-го типа ровно $$$n_i$$$;
  2. Каждый символ $$$i$$$-го типа окрашен в один из $$$c_i$$$ цветов;
  3. Строка может быть сведена к пустой строке путем многократного удаления $$$d_i$$$ последовательных символов $$$i$$$-го типа, имеющих одинаковый цвет.

Вычислите количество всех допустимых цветных строк, по модулю $$$998\,244\,353$$$.

Две окрашенные строки считаются разными, если они различаются хотя бы в одной позиции (либо по типу символа, либо по цвету).

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — количество типов.

В $$$i$$$-й из следующих $$$m$$$ строк содержатся $$$n_i, c_i, d_i$$$ ($$$1\le c_i \lt 998\,244\,353, 1\le n_i, d_i \le 10^8$$$) — общее количество символов $$$i$$$-го типа, количество цветов для этого типа и требуемая длина сокращения, соответственно.

Гарантируется, что сумма $$$\left\lceil\frac{n_i}{d_i}\right\rceil$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
2
2 1 1
1 2 1
2
2 2 2
2 1 2
2
6 2 3
5 3 2
Выходные данные
6
8
0
Примечание

Для примеров пронумеруем все цвета как $$$1, 2, \ldots, \sum_{j=1}^m c_j$$$. При этом цвета $$$1+\sum_{j=1}^{i-1} c_j,\ldots,\sum_{j=1}^i c_j$$$ относятся к $$$i$$$-му типу. Ниже цвета $$$1, 2, 3$$$ обозначены красным, синим и зелёным соответственно.

Для первого набора входных данных допустимыми строками являются:

  1. $$$[{\color{red}1}, {\color{red}1}, {\color{blue}2}]$$$
  2. $$$[{\color{red}1}, {\color{red}1}, {\color{green}3}]$$$
  3. $$$[{\color{red}1}, {\color{blue}2}, {\color{red}1}]$$$
  4. $$$[{\color{red}1}, {\color{green}3}, {\color{red}1}]$$$
  5. $$$[{\color{blue}2}, {\color{red}1}, {\color{red}1}]$$$
  6. $$$[{\color{green}3}, {\color{red}1}, {\color{red}1}]$$$

Для любой из этих строк мы можем сначала удалить единственные $$$2$$$ или $$$3$$$, а затем удалить $$$2$$$ последовательных $$$1$$$.

Для второго набора входных данных допустимыми строками являются:

  1. $$$[{\color{red}1}, {\color{red}1}, {\color{green}3}, {\color{green}3}]$$$
  2. $$$[{\color{red}1}, {\color{green}3}, {\color{green}3}, {\color{red}1}]$$$
  3. $$$[{\color{blue}2}, {\color{blue}2}, {\color{green}3}, {\color{green}3}]$$$
  4. $$$[{\color{blue}2}, {\color{green}3}, {\color{green}3}, {\color{blue}2}]$$$
  5. $$$[{\color{green}3}, {\color{red}1}, {\color{red}1}, {\color{green}3}]$$$
  6. $$$[{\color{green}3}, {\color{blue}2}, {\color{blue}2}, {\color{green}3}]$$$
  7. $$$[{\color{green}3}, {\color{green}3}, {\color{red}1}, {\color{red}1}]$$$
  8. $$$[{\color{green}3}, {\color{green}3}, {\color{blue}2}, {\color{blue}2}]$$$

Для третьего набора входных данных легко видно, что допустимых строк нет.