Contest Duration: - (local time) (150 minutes) Back to Home
C - Neither AB nor BA /

Time Limit: 4 sec / Memory Limit: 1024 MB

問題文

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

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

制約

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

入力

N


入力例 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