[AGC040C] Neither AB nor BA

### 题目描述 给出一个大于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`'外，其余所有的字符串皆为合法字符串。

[problemUrl]: https://atcoder.jp/contests/agc040/tasks/agc040_c 正の偶数 $ N $ が与えられます． `A`,`B`,`C` のみからなる長さ $ N $ の文字列 $ s $ であって，次の条件を満たすものの個数を求めてください． - 以下の操作を繰り返すことで，$ s $ を空文字列へと変換できる． - $ s $ の中で連続した $ 2 $ 文字を選び，消す．ただし，選んだ $ 2 $ 文字が `AB` または `BA` であってはいけない． 例えば，$ N=4 $ のとき，`ABBC` は条件をみたします． `ABBC` →（ `BB` を消去）→ `AC` →（ `AC` を消去 ）→ 空文字列 と操作すれば良いです． なお，答えは非常に大きくなることがあるので $ 998244353 $ で割ったあまりを求めてください．

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

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

2

7

10

50007

1000000

210055358

### 制約 - $ 2\ \leq\ N\ \leq\ 10^7 $ - $ N $ は偶数 ### Sample Explanation 1 $ s= $`AB`,`BA` 以外の文字列は条件を満たします．