分数: 800 点
问题陈述
给定的是正偶数 N.
查找字符串的数量
重复以下操作即可将 s 长度 N 组成 A, B,和 C 满足以下条件:
- s 转换为空字符串:
- 选择两个连续的字符 s 并删除它们。然而,选择
不允许
ABorBA。
- 选择两个连续的字符 s 并删除它们。然而,选择
不允许
例如, ABBC 满足条件 N=4,因为我们可以将其转换如下: ABBC →(擦除 BB) → AC →(擦除 AC) → (empty).
答案可能很大,因此计算计数模数 998244353.
约束
- 2 \leq N \leq 10^7
- N 是偶数。
输入
输入由标准输入按以下格式给出:
N
输出
打印满足条件的字符串数量,取模 998244353.
示例输入 1
2
示例输出 1
7
除外 AB 和 BA,所有可能的字符串都满足条件。
示例输入 2
10
示例输出 2
50007
示例输入 3
1000000
示例输出 3
210055358