output_description: Print the number, modulo 998244353, of ways to paint each of the integers red,
  green or blue so that the condition is satisfied.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1
      :
      a_N
attempt: import sys
  
  stdin = sys.stdin
  
  sys.setrecursionlimit(10**5)
  
  
  def li():
      return map(int, stdin.readline().split())
  
  
  def li_():
      return map(lambda x: int(x) - 1, stdin.readline().split())
  
  
  def lf():
      return map(float, stdin.readline().split())
  
  
  def ls():
      return stdin.readline().split()
  
  
  def ns():
      return stdin.readline().rstrip()
  
  
  def lc():
      return list(ns())
  
  
  def ni():
      return int(stdin.readline())
  
  
  def nf():
      return float(stdin.readline())
  
  
  n = ni()
  a = [ni() for _ in range(n)]
  
  suma = sum(a)
  MOD = 998244353
  
  dp_rgb = [[0] * (suma + 1) for _ in range(n + 1)]
  dp_gb = [[0] * (suma + 1) for _ in range(n + 1)]
  
  dp_rgb[0][0] = 1
  dp_gb[0][0] = 1
  
  for i, ai in enumerate(a):
      for sm in range(suma + 1):
          if sm + ai <= suma:
              dp_rgb[i + 1][sm + ai] += dp_rgb[i][sm] % MOD
              dp_gb[i + 1][sm + ai] += dp_gb[i][sm] % MOD
  
          dp_rgb[i + 1][sm] += 2 * dp_rgb[i][sm] % MOD
          dp_gb[i + 1][sm] += dp_gb[i][sm] % MOD
  
  ng = 3 * sum(dp_rgb[n][-(-suma // 2) :]) % MOD
  ok = 0 if suma % 2 else 3 * dp_gb[n][suma // 2] % MOD
  
  print((pow(3, n, MOD) - ng + ok) % MOD)
  
problem_description: Statement
  
  You are given N integers. The i-th integer is a_i. Find the number, modulo
  998244353, of ways to paint each of the integers red, green or blue so that
  the following condition is satisfied:
  
    * Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.
samples: [{"input": "4\n    1\n    1\n    1\n    2", "output": "18\n    \n\nWe can only paint the integers so that the lengths of the sides of the\ntriangle will be 1, 2 and 2, and there are 18 such ways.\n\n* * *"}, {"input": "6\n    1\n    3\n    2\n    3\n    5\n    2", "output": "150\n    \n\n* * *"}, {"input": "20\n    3\n    1\n    4\n    1\n    5\n    9\n    2\n    6\n    5\n    3\n    5\n    8\n    9\n    7\n    9\n    3\n    2\n    3\n    8\n    4", "output": "563038556"}]