AT_caddi2018_d Square

[problemUrl]: https://atcoder.jp/contests/caddi2018/tasks/caddi2018_d 高橋君は、$ N $ 行 $ N $ 列のマス目を持っています。マス目の上から $ i $ 番目、左から $ j $ 番目のマスは $ (i,j) $ で表されます。 特に、マス目の左上のマスは $ (1,1) $ であり、右下のマスは $ (N,N) $ です。 高橋君の持っているマス目のうち $ M $ 個のマスには、$ 0 $ または $ 1 $ の整数が書き込まれています。 整数が書き込まれたマスのうち $ i $ 番目のマスの情報は $ 3 $ つの整数 $ a_i,b_i,c_i $ で表され、マス $ (a_i,b_i) $ に整数 $ c_i $ が書き込まれていることを表します。 高橋君は、以下の条件を満たすように残りのマスに $ 0 $ または $ 1 $ の整数を書き込むことにしました。 書き込み方としてありうるものの個数を $ 998244353 $ で割ったあまりを求めてください。 - 任意の $ 1\leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ : $ $ a_M $ $ b_M $ $ c_M $

書き込み方としてありうるものの個数を $ 998244353 $ で割ったあまりを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ M\ \leq\ min(5\ \times\ 10^4,N^2) $ - $ 1\ \leq\ a_i,b_i\ \leq\ N(1\leq\ i\leq\ M) $ - $ 0\ \leq\ c_i\ \leq\ 1(1\leq\ i\leq\ M) $ - $ i\ \neq\ j $ ならば $ (a_i,b_i)\ \neq\ (a_j,b_j) $ である - 入力はすべて整数である ### Sample Explanation 1 例えば、以下のような書き込み方が条件を満たします。 ``` 101 111 011 111 000 011 ```