output_description: Print the number of possible ways to write integers, modulo 998244353.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_1 b_1 c_1
      :
      a_M b_M c_M
attempt: N, M = map(int, input().split())
  mod = 998244353
  
  factorial = [1 for i in range(2 * N + 1)]
  for i in range(1, 2 * N + 1):
      if i == 1:
          factorial[i] = 1
      else:
          factorial[i] = factorial[i - 1] * i % mod
  
  
  def comb(n, k):
      return (factorial[n] * pow(factorial[n - k] * factorial[k], -1, mod)) % mod
  
  
  memo = [[0] * 2 for _ in range(N)]
  for i in range(M):
      a, b, c = map(int, input().split())
      memo[max(a, b) - 1][c] += 1
  
  ans = 0
  for i in range(N - 1, 0, -1):
      tmp = 0
      n_margin = 2 * (i + 1) - 1 - sum(memo[i])
      if (memo[i][1] - memo[i - 1][1]) % 2:
          if memo[i][1] % 2:
              for j in range(0, n_margin + 1, 2):
                  tmp += comb(n_margin, j)
          else:
              for j in range(1, n_margin + 1, 2):
                  tmp += comb(n_margin, j)
      else:
          if memo[i][1] % 2:
              for j in range(1, n_margin + 1, 2):
                  tmp += comb(n_margin, j)
          else:
              for j in range(0, n_margin + 1, 2):
                  tmp += comb(n_margin, j)
      print(i, n_margin, tmp, sum(memo[i]))
      ans += tmp
      ans %= mod
  
  print(ans)
  
problem_description: Statement
  
  Takahashi has an N \times N grid. The square at the i-th row and the j-th
  column of the grid is denoted by (i,j). Particularly, the top-left square of
  the grid is (1,1), and the bottom-right square is (N,N).
  
  An integer, 0 or 1, is written on M of the squares in the Takahashi's grid.
  Three integers a_i,b_i and c_i describe the i-th of those squares with
  integers written on them: the integer c_i is written on the square (a_i,b_i).
  
  Takahashi decides to write an integer, 0 or 1, on each of the remaining
  squares so that the condition below is satisfied. Find the number of such ways
  to write integers, modulo 998244353.
  
    * For all 1\leq i < j\leq N, there are even number of 1s in the square region whose top-left square is (i,i) and whose bottom-right square is (j,j).
samples: [{"input": "3 3\n    1 1 1\n    3 1 0\n    2 3 1", "output": "8\n    \n\nFor example, the following ways to write integers satisfy the condition:\n\n    \n    \n    101   111\n    011   111\n    000   011\n    \n\n* * *"}, {"input": "4 5\n    1 3 1\n    2 4 0\n    2 3 1\n    4 2 1\n    4 4 1", "output": "32\n    \n\n* * *"}, {"input": "3 5\n    1 3 1\n    3 3 0\n    3 1 0\n    2 3 1\n    3 2 1", "output": "0\n    \n\n* * *"}, {"input": "4 8\n    1 1 1\n    1 2 0\n    3 2 1\n    1 4 0\n    2 1 1\n    1 3 0\n    3 4 1\n    4 4 1", "output": "4\n    \n\n* * *"}, {"input": "100000 0", "output": "342016343"}]