output_description: Print the minimum number of stones that needs to be recolored.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S
attempt: N = int(input())
  mod = 998244353
  # DP ナップサックぽいやつ
  # DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
  # 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
  # DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る
  
  aaa = [int(input()) for _ in range(N)]
  sum_aaa = sum(aaa)
  
  sum_now = 0
  DP = [[0] * (sum_aaa + 1) for i in range(N)]
  DP2 = [[0] * (sum_aaa + 1) for i in range(N)]
  
  a = aaa[0]
  DP[0][0] = 2
  DP[0][a] = 1
  
  DP2[0][0] = 1
  DP2[0][a] = 1
  
  sum_now += a
  
  for i in range(1, N):
      a = aaa[i]
      sum_now += a
      for j in range(sum_now + 1):
  
          if j >= a:
              DP[i][j] = DP[i - 1][j] * 2 + DP[i - 1][j - a]
          else:
              DP[i][j] = DP[i - 1][j] * 2
  
          while DP[i][j] > mod:
              DP[i][j] -= mod
  
      for j in range(min(sum_now + 1, int(sum_aaa / 2) + 1)):
          if j >= a:
              DP2[i][j] = DP2[i - 1][j] + DP2[i - 1][j - a]
          else:
              DP2[i][j] = DP2[i - 1][j]
  
          while DP2[i][j] > mod:
              DP2[i][j] -= mod
  
  # print(DP2)
  minimum_invalid_length = int((sum_now + 1) // 2)
  num_too_long = sum(DP[N - 1][minimum_invalid_length:])
  if sum_aaa % 2 == 0:
      num_too_long -= DP2[N - 1][int(sum_aaa / 2)]
  # print(num_too_long)
  # print(sum(aaa))
  print((3**N - num_too_long * 3) % mod)
  
problem_description: Statement
  
  There are N stones arranged in a row. Every stone is painted white or black. A
  string S represents the color of the stones. The i-th stone from the left is
  white if the i-th character of S is `.`, and the stone is black if the
  character is `#`.
  
  Takahashi wants to change the colors of some stones to black or white so that
  there will be no white stone immediately to the right of a black stone. Find
  the minimum number of stones that needs to be recolored.
samples: [{"input": "3\n    #.#", "output": "1\n    \n\nIt is enough to change the color of the first stone to white.\n\n* * *"}, {"input": "5\n    #.##.", "output": "2\n    \n\n* * *"}, {"input": "9\n    .........", "output": "0"}]