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: def main():
      mod = 998244353
      n = int(input())
      Fact = [1]
      for i in range(1, n + 1):
          Fact.append(Fact[i - 1] * i % mod)
      Finv = [0] * (n + 1)
      Finv[-1] = pow(Fact[-1], mod - 2, mod)
      for i in range(n - 1, -1, -1):
          Finv[i] = Finv[i + 1] * (i + 1) % mod
  
      def comb(n, r):
          if n < r:
              return 0
          return Fact[n] * Finv[r] * Finv[n - r] % mod
  
      impossible = 0
      for k in range(n // 2 + 1, n + 1):
          impossible += comb(n, k) * pow(2, n - k, mod)
          impossible %= mod
      print(pow(3, n, mod) - impossible * 2)
  
  
  if __name__ == "__main__":
      main()
  
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"}]