問題文

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

• L_i 文字目から R_i 文字目の間に文字 C_i が存在する

制約

• 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)
• 入力は全て整数

小課題

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 点) 追加の制約はない

入力例 1

3 2
1 3 0
1 2 1

出力例 1

5

010、011、100、101、110 の 5 つが条件を満たす文字列です。

入力例 2

5 4
1 2 0
2 3 0
3 4 0
4 5 0

出力例 2

13

10101 や 00000 など合計 13 個の文字列が条件を満たします。

入力例 3

7 9
4 6 0
1 2 0
5 7 1
3 4 0
7 7 0
6 7 1
2 5 1
3 5 0
1 7 1

出力例 3

13