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: def main():
      N = int(input())
      A = [0] * N
      MOD = 998244353
      summation = 0
  
      for i in range(N):
          A[i] = int(input())
          summation += A[i]
  
      # dp[i][j] represents sum of red is j at i position
      dp = [[0 for _ in range(summation + 1)] for _ in range(N)]
      dp[0][0] = 2  # green or blue
      dp[0][A[0]] = 1  # red
  
      for i in range(1, N):
          for j in range(len(dp[i])):
              dp[i][j] += (
                  dp[i - 1][j] * 2 % MOD
              )  # don't use A[i] for red, i.e. use green or blue
              dp[i][j] += (
                  dp[i - 1][j - A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0
              )  # use i red
  
      # total
      ans = (3**N) % MOD
      ceil = summation // 2
      if summation % 2 != 0:
          ceil += 1
      ans -= sum([dp[N - 1][r] for r in range(ceil, summation + 1)]) * 3
      ans %= MOD
  
      if summation % 2 == 0:
          # case r = g = S/2
          dp = [[0 for _ in range(summation // 2 + 1)] for _ in range(N)]
          dp[0][0] = 1  # only blue
          dp[0][A[0]] = 1
          for i in range(1, N):
              for j in range(len(dp[i])):
                  dp[i][j] += dp[i - 1][j] % MOD
                  dp[i][j] += (
                      dp[i - 1][j - A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0
                  )
          ans += dp[N - 1][summation // 2] * 3
          ans %= MOD
  
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
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"}]