C - Neither AB nor BA Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

正の偶数 N が与えられます． A,B,C のみからなる長さ N の文字列 s であって，次の条件を満たすものの個数を求めてください．

  • 以下の操作を繰り返すことで，s を空文字列へと変換できる．
    • s の中で連続した 2 文字を選び，消す．ただし，選んだ 2 文字が AB または BA であってはいけない．

例えば，N=4 のとき，ABBC は条件をみたします． ABBC →（ BB を消去）→ AC →（ AC を消去 ）→ 空文字列 と操作すれば良いです．

なお，答えは非常に大きくなることがあるので 998244353 で割ったあまりを求めてください．

制約

  • 2 \leq N \leq 10^7
  • N は偶数

入力

入力は以下の形式で標準入力から与えられる．

N

出力

条件をみたす文字列が何通りあるかを 998244353 で割ったあまりを出力せよ．

入力例 1

2

出力例 1

7

s=AB,BA 以外の文字列は条件を満たします．

入力例 2

10

出力例 2

50007

入力例 3

1000000

出力例 3

210055358

Score : 800 points

Problem 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.

Constraints

  • 2 \leq N \leq 10^7
  • N is an even number.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of strings that satisfy the conditions, modulo 998244353.

Sample Input 1

2

Sample Output 1

7

Except AB and BA, all possible strings satisfy the conditions.

Sample Input 2

10

Sample Output 2

50007

Sample Input 3

1000000

Sample Output 3

210055358