output_description: Print the number of the pairs of a subset of the rows and a subset of the
  columns that satisfy the condition, modulo 998244353.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_{11} ... a_{1M}
      :
      a_{N1} ... a_{NM}
attempt: #!/usr/bin/env python3
  import sys, os
  
  try:
      from typing import Any, Union, List, Tuple, Dict
  except ImportError:
      pass
  sys.setrecursionlimit(10**6)
  if os.environ.get("USER") == "shun":
  
      def debug(*args):
          print(*args, file=sys.stderr)
  
  else:
      print("NO DEBUG", file=sys.stderr)
  
      def debug(*args):
          pass
  
  
  def exit():
      sys.exit(0)
  
  
  l = int(input())
  a = []
  for _ in range(l):
      a.append(int(input()))
  
  init_score = 0
  for i in range(l):
      if a[i] == 0:
          init_score += 2
      elif a[i] % 2 == 0:
          pass
      else:
          init_score += 1
  
  left = [0]
  for i in range(l):
      left.append(left[i])
      if a[i] == 0:
          left[i + 1] -= 2
      elif a[i] % 2 == 0:
          left[i + 1] += a[i]
      else:
          left[i + 1] += a[i] - 1
  left_i = 0
  left_min = left[0]
  for i in range(l + 1):
      if left[i] < left_min:
          left_i = i
          left_min = left[i]
  debug(left_i, left)
  
  right = [0] * (l + 1)
  for i in range(l, 0, -1):
      right[i - 1] = right[i]
      if a[i - 1] == 0:
          right[i - 1] -= 2
      elif a[i - 1] % 2 == 0:
          right[i - 1] += a[i - 1]
      else:
          right[i - 1] += a[i - 1] - 1
  right_i = 0
  right_min = right[0]
  for i in range(l + 1):
      if right[i] < right_min:
          right_i = i
          right_min = right[i]
  debug(right_i, right)
  
  
  # odd
  temp_score = init_score + left_min + right_min
  b = a[left_i:right_i]
  k = len(b)
  
  for i in range(k):
      if b[i] == 0:
          temp_score -= 1
      elif b[i] % 2 == 0:
          temp_score += 1
      else:
          temp_score -= 1
  
  
  left = [0]
  for i in range(k):
      left.append(left[i])
      if b[i] == 0:
          left[i + 1] += 1
      elif b[i] % 2 == 0:
          left[i + 1] -= 1
      else:
          left[i + 1] += 1
  left_i = 0
  left_min = left[0]
  for i in range(k + 1):
      if left[i] < left_min:
          left_i = i
          left_min = left[i]
  debug(left_i, left)
  
  right = [0] * (k + 1)
  for i in range(k, 0, -1):
      right[i - 1] = right[i]
      if b[i - 1] == 0:
          right[i - 1] += 1
      elif b[i - 1] % 2 == 0:
          right[i - 1] -= 1
      else:
          right[i - 1] += 1
  right_i = 0
  right_min = right[0]
  for i in range(k + 1):
      if right[i] < right_min:
          right_i = i
          right_min = right[i]
  debug(right_i, right)
  
  score = temp_score + left_min + right_min
  print(score)
  
problem_description: Statement
  
  There is a square grid with N rows and M columns. Each square contains an
  integer: 0 or 1. The square at the i-th row from the top and the j-th column
  from the left contains a_{ij}.
  
  Among the 2^{N+M} possible pairs of a subset A of the rows and a subset B of
  the columns, find the number of the pairs that satisfy the following
  condition, modulo 998244353:
  
    * The sum of the |A||B| numbers contained in the intersection of the rows belonging to A and the columns belonging to B, is odd.
samples: [{"input": "2 2\n    0 1\n    1 0", "output": "6\n    \n\nFor example, if A consists of the first row and B consists of both columns,\nthe sum of the numbers contained in the intersection is 0+1=1.\n\n* * *"}, {"input": "2 3\n    0 0 0\n    0 1 0", "output": "8"}]