AT_agc040_c [AGC040C] Neither AB nor BA
Description
[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 $ で割ったあまりを求めてください.
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 2\ \leq\ N\ \leq\ 10^7 $
- $ N $ は偶数
### Sample Explanation 1
$ s= $`AB`,`BA` 以外の文字列は条件を満たします.