output_description: Print the number of strings that satisfy the conditions, modulo 998244353.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: #!/usr/bin/env python3
  import sys
  
  sys.setrecursionlimit(10**8)
  input = sys.stdin.readline
  
  MOD = 998244353
  MAX_N = 10**6
  
  fac = [1] + [0] * MAX_N
  fac_inv = [1] + [0] * MAX_N
  mod_pow2_n = [1] + [0] * MAX_N
  f = 1
  finv = 1
  p2 = 1
  for i in range(1, MAX_N + 1):
      # fac[i] = fac[i-1] * i % MOD
      f *= i
      f %= MOD
      fac[i] = f
      # Fermat's little theorem says
      # a**(p-1) mod p == 1
      # then, a * a**(p-2) mod p == 1
      # it means a**(p-2) is inverse element
      # fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD
      finv *= pow(i, MOD - 2, MOD)
      finv %= MOD
      fac_inv[i] = finv
      p2 *= 2
      p2 %= MOD
      mod_pow2_n[i] = p2
  
  
  def mod_nCr(n, r):
      if n < r or n < 0 or r < 0:
          return 0
      tmp = fac_inv[n - r] * fac_inv[r] % MOD
      return tmp * fac[n] % MOD
  
  
  def single_mod_nCr(n, r):
      if n < r or n < 0 or r < 0:
          return 0
      if r > n - r:
          r = n - r
      ret = 1
      for i in range(r):
          ret *= n - i
          ret *= pow(i + 1, MOD - 2, MOD)
          ret %= MOD
      return ret
  
  
  n = int(input())
  ans = 0
  for i in range(n // 2 + 1, n + 1):
      ans += mod_nCr(n, i) * mod_pow2_n[n - i]
      ans %= MOD
  print((pow(3, n, MOD) - ans * 2 + MOD) % MOD)
  
problem_description: Statement
  
  Given is a positive even number N.
  
  Find the number of strings s of length N consisting of `A`, `B`, and `C` that
  satisfy the following condition:
  
    * s can be converted to the empty string by repeating the following operation:
      * Choose two consecutive characters in s and erase them. However, choosing `AB` or `BA` is not allowed.
  
  For example, `ABBC` satisfies the condition for N=4, because we can convert it
  as follows: `ABBC` → (erase `BB`) → `AC` → (erase `AC`) → `(empty)`.
  
  The answer can be enormous, so compute the count modulo 998244353.
samples: [{"input": "2", "output": "7\n    \n\nExcept `AB` and `BA`, all possible strings satisfy the conditions.\n\n* * *"}, {"input": "10", "output": "50007\n    \n\n* * *"}, {"input": "1000000", "output": "210055358"}]