AT_abc466_g [ABC466G] Segment Sum Constraints

$ 3 $ つの整数の組 $ (L_i,R_i,S_i) $ が $ M $ 個与えられます。 $ N $ 個の**正の**整数の組 $ A=(A_1,A_2,\ldots,A_N) $ であって、次の条件をすべてみたすものを考えます。 - $ A_{L_i}, A_{L_i+1}, \ldots, A_{R_i} $ の総和は $ S_i $ である。 条件をみたす組が無限に存在する場合は `Infinity` を、そうでない場合はその数を $ 998244353 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ S_1 $ $ L_2 $ $ R_2 $ $ S_2 $ $ \vdots $ $ L_M $ $ R_M $ $ S_M $

条件をみたす組が無限に存在する場合は `Infinity` を、そうでない場合はその数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 条件は以下の $ 2 $ つです。 - $ 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 $ を出力します。 ### Sample Explanation 2 条件をみたす $ A $ は無数に存在します。 ### Sample Explanation 3 条件をみたす $ A $ は存在しません。 ### 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 $ - $ (L_i,R_i) $ はすべて異なる。 - 入力される値はすべて整数