AT_pakencamp_2022_day3_f Cycle and Xor

$ 0 $ 以上 $ 2^M $ 未満の整数からなる長さ $ N $ の数列 $ A=(A_0,A_1,\ldots,A_{N-1}) $ であって、以下の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - すべての整数 $ i\ (0 \le i \le N-1) $ について、 $ A_i \oplus A_{(i+1) \bmod N} \neq T_i $ かつ $ A_i \oplus A_{(i+1) \bmod N} \neq U_i $ が成り立つ ただし $ \oplus $ はビット単位 $ \mathrm{XOR} $ 演算を表します。 ビット単位 $ \mathrm{XOR} $ 演算とは非負整数 $ A,B $ のビット単位 $ \mathrm{XOR} $ 演算、 $ A\oplus B $ は、以下のように定義されます。 - $ A\oplus B $ を二進表記した際の $ 2^k\ (k\geq 0) $ の位の数は、 $ A,B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3\oplus 5 = 6 $ となります（二進表記すると: $ 011\oplus 101 = 110 $ )。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ T_0 $ $ U_0 $ $ T_1 $ $ U_1 $ $ \vdots $ $ T_{N-1} $ $ U_{N-1} $

答えを出力せよ。

### Sample Explanation 1 $ A $ としてありうるのは $ (0,2,1),(0,3,0),(1,3,0),(1,2,1),(2,0,3),(2,1,2),(3,1,2),(3,0,3) $ の $ 8 $ 通りです。 ### Constraints - $ 2 \le N \le 2\times 10^5 $ - $ 1 \le M \le 30 $ - $ 0 \le T_i < U_i < 2^M $ - 入力は全て整数