题目描述

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

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

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

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

输入格式

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

$N$

输出格式

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

题目大意

题目描述

给出一个大于0的偶数 $N$ 。

请找出长度为 $N$ ，由'A'，'B'，'C'这三个字母组成且可以由下列规则把其变为空串的字符串 $s$ 的数量。

• 不断选择$s$中任意除'AB'和'BA'外的长度为2的子串并删除。

比如'ABBC'是$N=4$条件下的一个合法字符串，因为我们可以通过这样的方式将其变为空串：
'ABBC'→（删除'BB'）→'AC'→（删除'AC'）→'(空串)'

答案可能很大，所以请将结果对$998244353$取模。

数据范围

• $2 \le N \le 10^7$
• $N$ 是偶数

样例1解释

除了'AB'和'BA'外，其余所有的字符串皆为合法字符串。

2

7

10

50007

1000000

210055358

提示

制約

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

Sample Explanation 1

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