AT_abc466_g.Segment Sum Constraints

You are given $M$ triples of integers $(L_i,R_i,S_i)$.
Consider tuples $A=(A_1,A_2,\ldots,A_N)$ of $N$ positive integers satisfying all of the following conditions.

• The sum of $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ is $S_i$.

If there are infinitely many tuples satisfying the conditions, output Infinity; otherwise, output the number of such tuples, modulo $998244353$.

给你 $M$ 个整数三元组 $(L_i,R_i,S_i)$。
考虑由 $N$ 个正整数构成的元组 $A=(A_1,A_2,\ldots,A_N)$，要求其满足以下所有条件：

• $A_{L_i} + A_{L_i+1} + \cdots + A_{R_i} = S_i$。

若满足条件的元组有无穷多个，则输出 Infinity；否则，输出满足条件的元组个数对 $998244353$ 取模的结果。

The input is given from Standard Input in the following format:

$N$ $M$
$L_1$ $R_1$ $S_1$
$L_2$ $R_2$ $S_2$
$\vdots$
$L_M$ $R_M$ $S_M$

输入从标准输入中按以下格式给出：

$N$ $M$
$L_1$ $R_1$ $S_1$
$L_2$ $R_2$ $S_2$
$\vdots$
$L_M$ $R_M$ $S_M$

If there are infinitely many tuples satisfying the conditions, output Infinity; otherwise, output the number of such tuples, modulo $998244353$.

如果满足条件的元组有无穷多个，则输出 Infinity；否则，输出满足条件的元组个数对 $998244353$ 取模的结果。

Sample 1 Explanation:
We have the following two conditions.

• $A_1+A_2=7$
• $A_2+A_3=10$

The six tuples $A=(1,6,4), (2,5,5), (3,4,6), (4,3,7), (5,2,8), (6,1,9)$ satisfy the conditions, so output $6$ modulo $998244353$, that is, output $6$.

Sample 2 Explanation:
There are infinitely many tuples $A$ satisfying the conditions.

Sample 3 Explanation:
There is no tuple $A$ satisfying the conditions.

Constraints

• $1 \leq N \leq 8$
• $1 \leq M \leq 36$
• $1\leq L_i\leq R_i\leq N$
• $1\leq S_i\leq 10^9$
• All $(L_i,R_i)$ are distinct.
• All input values are integers.

样例 1 解释：
我们有以下两个条件：

• $A_1+A_2=7$
• $A_2+A_3=10$

满足条件的六元组 $A=(1,6,4), (2,5,5), (3,4,6), (4,3,7), (5,2,8), (6,1,9)$ 共有 6 个，因此输出 $6$ 对 $998244353$ 取模的结果，即输出 $6$。

样例 2 解释：
满足条件的元组 $A$ 有无穷多个。

样例 3 解释：
不存在满足条件的元组 $A$。

约束条件

• $1 \leq N \leq 8$
• $1 \leq M \leq 36$
• $1\leq L_i\leq R_i\leq N$
• $1\leq S_i\leq 10^9$
• 所有 $(L_i,R_i)$ 互不相同。
• 所有输入值均为整数。