Ena 的曲绘（set）

题目背景

Ena 正在为「25 点，Nightcord 见。」的新歌制作曲绘。

曲绘的最下方有一些格子，Ena 希望先将一些格子涂上某种颜色，再将这些涂色的格子复制粘贴后改为新的颜色，一条五彩斑斓的飘带就做完了。

但是 Ena 对艺术品有着完美的追求：她认为艺术与数学不约而同地具有着协调的美——对她自己的作品也是如此。

Ena 知道，如果自己涂了 $n$ 个格子，复制了 $m$ 次，那么最多会有 $nm$ 个格子被染色。要是恰好能将连续的 $nm$ 个格子都不重不漏地染上了颜色……

拿起数位板的画笔，Ena 很快找到了一些简单的染色方法。你知道身为完美主义者的 Ena 一定会找出所有染色方法后再选出最好看的，于是你决定算出 Ena 今天晚上的睡觉时间。

题目描述

一个集合 $S$ 是好的，当且仅当存在另一个集合 $T$，使得 $(S,T)$ 满足以下条件：

• $|S|=n$，$|T|=m$，$1\in S$。
• $S\subseteq [1,nm]\cap\mathbb Z$，$T\subseteq\mathbb Z$。
• $\{i+j\mid i\in S, j\in T\}=\{1,2,\ldots,nm\}$。

给定 $n,m$，求好的集合数量对质数 $998244353$ 取模的值。

为了方便选手，$n$ 和 $m$ 都使用唯一分解形式给出。

输入格式

从文件 set.in 中读入数据。

第一行输入一个整数 $L$，代表质因数个数。

接下来 $L$ 行，每行输入三个整数 $p_i,x_i,y_i$，代表质数及其在 $n,m$ 上的指数。

给定的 $n,m$ 分别为

$$n=\prod p_i^{x_i},\qquad m=\prod p_i^{y_i}。$$

输出格式

输出到文件 set.out 中。

输出一个整数，代表好的集合数量对 $998244353$ 取模的值。

样例 1 输入

1
2 1 1

样例 1 输出

2

样例 1 解释

对于第一组样例，$n=2$，$m=2$，合法的集合为 $S_1=\{1,2\}$ 和 $S_2=\{1,3\}$，我们可以构造 $T_1=\{0,2\}$ 和 $T_2=\{0,1\}$。

样例 2 输入

2
2 1 1
3 1 0

样例 2 输出

4

样例 2 解释

对于第二组样例，$n=6$，$m=2$，合法的集合为

$$S_1=\{1,2,3,4,5,6\},$$ $$S_2=\{1,2,3,7,8,9\},$$ $$S_3=\{1,2,5,6,9,10\},$$ $$S_4=\{1,3,5,7,9,11\}。$$

样例 3 输入

3
2 2 2
3 2 2
5 1 0

样例 3 输出

4458

样例 3 解释

对于第三组样例，$n=2^2\cdot 3^2\cdot 5^1=180$，$m=2^2\cdot 3^2=36$。

样例 4

见选手目录下的 set/set4.in 与 set/set4.ans。

该样例数据范围满足测试点 $9,11$。

数据范围

本题共 $20$ 个测试点，全部测试点满足：

• $1\le n,m\le 10^{20080520}$；
• $p_i\in [2,998244353)$，且 $p_i$ 均为互不相同的素数；
• $\max(x_i,y_i)\ge 1$；
• $0\le \sum x_i,\sum y_i\le 2\times 10^5$。

对于编号为奇数的测试点，保证 $\min(x_i,y_i)=0$。

测试点	数据范围
$1$	$nm\le 10,\ \sum x_i\le 1$
$2$	$nm\le 10$
$3\sim 4$	$nm\le 20$
$5$	$nm\le 10^3,\ \sum x_i\le 1$
$6\sim 7$	$n,m\le 10^3$
$8$	$\sum x_i\le 1,\ \sum y_i\le 500$
$9\sim 11$	$\sum x_i,\sum y_i\le 500$
$12$	$\sum x_i\le 1,\ \sum y_i\le 5\times 10^3$
$13\sim 15$	$\sum x_i,\sum y_i\le 5\times 10^3$
$16$	$\sum x_i\le 1$
$17\sim 20$	无特殊限制