AT_pakencamp_2022_day2_d Binary Strings

`0` と `1` からなる長さ $ N $ の文字列であって $ 1 $ 以上 $ M $ 以下の全ての整数 $ i $ について次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ L_i $ 文字目から $ R_i $ 文字目の間に文字 $ C_i $ が存在する

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

答えを $ 1 $ 行に出力せよ。

### 小課題 1. ( $ 50 $ 点) $ N\leq 16, M\leq 16 $ 2. ( $ 100 $ 点) $ N\leq 2000, M\leq 2000, C_i=0\,(1\leq i\leq M) $ 3. ( $ 150 $ 点) $ C_i=0\,(1\leq i\leq M) $ 4. ( $ 300 $ 点) 追加の制約はない ### Sample Explanation 1 `010`、`011`、`100`、`101`、`110` の $ 5 $ つが条件を満たす文字列です。 ### Sample Explanation 2 `10101` や `00000` など合計 $ 13 $ 個の文字列が条件を満たします。 ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ 1\leq M\leq 2\times 10^5 $ - $ 1\leq L_i\leq R_i\leq N\,(1\leq i\leq M) $ - $ C_i\in\lbrace 0,1\rbrace\,(1\leq i\leq M) $ - 入力は全て整数