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: mod = 998244353
  
  
  def main():
      # start coding here...
      # Three colors
      N = int(input())
      A = [int(input()) for i in range(N)]
      M = (sum(A) - 1) // 2
      S = sum(A)
      # 1<= R,G,B<= S, R+ G + B = S
      # ほうじょ原理
      Alls = pow(3, N, mod)
      # R,G,B　のうち1つ以上が S より大のケース case2
      case2 = 0
      # dp[x][i] := 初めのｘこを塗り分けて、Rの値がiになるものの個数
      dp = [[0 for i in range(90001)] for j in range(N + 1)]
      dp[0][0] = 1
      for i in range(1, N + 1):
          v = A[i - 1]
          for j in range(90001):
              if j >= v:
                  dp[i][j] = dp[i - 1][j - v] + 2 * dp[i - 1][j]
              else:
                  dp[i][j] = 2 * dp[i - 1][j]
              dp[i][j] %= mod
  
      if S % 2 != 0:
          # R,G,B のうち1つだけがSより大きい
          for i in range(M + 1, 90001):
              case2 += 3 * dp[N][i]
              case2 %= mod
      if S % 2 == 0:
          # R,G,B のうち1つがSより大きい
          for i in range(M + 1, 90001):
              case2 += 3 * dp[N][i]
              case2 %= mod
          # R,G,B のうち2つがS//2
          # sub_dp[x][v]:= 初めのxこを塗り分けて　Rの方をvにする方法
          sub_dp = [[0 for i in range(90001)] for j in range(N + 1)]
          sub_dp[0][0] = 1
          for i in range(1, N + 1):
              v = A[i - 1]
              for j in range(90001):
                  if j >= v:
                      sub_dp[i][j] = sub_dp[i - 1][j] + sub_dp[i - 1][j - v]
                  else:
                      sub_dp[i][j] = sub_dp[i - 1][j]
                  sub_dp[i][j] %= mod
          case2 -= 3 * sub_dp[N][S // 2]
          case2 %= mod
      ans = Alls - case2
      print(ans % mod)
      return
  
  
  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"}]