AT_abc466_g [ABC466G] 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 $ .

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 $

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

### Sample Explanation 1 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 Explanation 2 There are infinitely many tuples $ A $ satisfying the conditions. ### Sample Explanation 3 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.