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: N = int(input())
  
  total = 0
  A = []
  for i in range(N):
      a = int(input())
      total += a
      A.append(a)
  
  mod = 998244353
  
  dp = [[0] * 91000 for i in range(N + 1)]
  dp[0][0] = 1
  for i in range(1, N + 1):
      for j in range(300 * i, -1, -1):
          dp[i][j + A[i - 1]] += dp[i - 1][j]
          dp[i][j + A[i - 1]] %= mod
          dp[i][j] += 2 * dp[i - 1][j]
          dp[i][j] %= mod
  
  exc = 0
  for j in range((total + 1) // 2, total + 1):
      exc += dp[N][j]
      exc %= mod
  
  res = (3**N % mod) - exc * 3
  
  if total % 2 == 0:
      dp = [[0] * 91000] * (N + 1)
      for i in range(1, N + 1):
          for j in range(300 * i, 0, -1):
              dp[i][j + A[i - 1]] += dp[i - 1][j]
              dp[i][j + A[i - 1]] %= mod
              dp[i][j] += dp[i - 1][j]
              dp[i][j] %= mod
      res += dp[N][total / 2] * 3
  
  print(res % 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"}]