CF2223F.Zhily and Colorful Strings

Since Jily's first birthday, Zhily has given him a colored string as a gift each year, and each year's gift has been different from all previous ones. This year, Jily was amazed to discover that he has received every possible distinct gift!

We call a colored string that meets the following conditions valid:

1. It consists of $m$ types of characters, with exactly $n_i$ characters of the $i$-th type;
2. Each character of the $i$-th type is colored with one of $c_i$ colors;
3. The string can be reduced to an empty string by repeatedly deleting $d_i$ consecutive characters of the $i$-th type that share the same color.

Calculate the number of all valid colored strings, modulo $998\,244\,353$.

Two colored strings are considered different if they differ in at least one position (either in character type or in color).

自从吉莉一岁生日起，芝莉每年都会送他一根彩色字符串作为礼物，且每年的礼物都与之前所有礼物不同。今年，吉莉惊讶地发现，他已收齐了所有可能的、互不相同的礼物！

我们称满足以下条件的彩色字符串为有效字符串：

1. 它由 $m$ 种字符类型组成，其中第 $i$ 种类型恰好出现 $n_i$ 次；
2. 第 $i$ 种类型的每个字符可被染上 $c_i$ 种颜色之一；
3. 该字符串可通过重复执行如下操作缩减为空字符串：每次删除 $d_i$ 个连续的、同属第 $i$ 种类型、且颜色相同的字符。

请计算所有有效彩色字符串的总数，结果对 $998\,244\,353$ 取模。

若两个彩色字符串在至少一个位置上不同（字符类型不同，或颜色不同），则视为不同的字符串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $m$ ($1\le m\le 2\cdot 10^5$) — the number of types.

The $i$-th of the next $m$ lines contains $n_i, c_i, d_i$ ($1\le c_i \lt 998\,244\,353, 1\le n_i, d_i \le 10^8$) — the total count of characters of the $i$-th type, the number of colors for this type, and the required reduction length, respectively.

It is guaranteed that the sum of $\left\lceil\frac{n_i}{d_i}\right\rceil$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $m$（$1\le m\le 2\cdot 10^5$）—— 表示字符类型的种类数。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $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$。

For each test case, output one integer in one line, representing the number of valid colored strings, modulo $998\,244\,353$.

对于每个测试用例，在一行中输出一个整数，表示合法的染色字符串的数量，对 $998\,244\,353$ 取模。

For the examples, let's number all the colors by $1, 2, \ldots, \sum_{j=1}^m c_j$. Where the colors $1+\sum_{j=1}^{i-1} c_j,\ldots,\sum_{j=1}^i c_j$ are of the $i$-th type. Below, the color $1, 2, 3$ are colored red, blue, and green, respectively.

For the first test case, the valid strings are:

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}]$

For any of these strings, we can first remove the only $2$ or $3$, and then remove the $2$ consecutive $1$s.

For the second test case, the valid strings are:

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}]$

For the third test case, it can be easily seen that there are no valid strings.

对于示例，我们将所有颜色编号为 $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$，再移除两个相邻的 $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}]$

对于第三个测试用例，显然不存在合法的字符串。