题目描述

给定一个正的偶数 $N$。请计算满足以下条件的长度为 $N$、仅由 A、B、C 组成的字符串 $s$ 的个数：

• 可以通过重复以下操作将 $s$ 变为空字符串：
  • 从 $s$ 中选择连续的 $2$ 个字符并将其删除。只要所选的 $2$ 个字符不是 AB 或 BA 即可。

例如，当 $N=4$ 时，ABBC 满足条件。可以按如下操作：ABBC →（删除 BB）→ AC →（删除 AC）→ 空字符串。

注意，答案可能非常大，请输出对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$

输出格式

输出满足条件的字符串个数对 $998244353$ 取模的结果。

样例 1

输入

2

输出

7

样例 2

输入

10

输出

50007

样例 3

输入

1000000

输出

210055358

说明/提示

限制

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

样例解释 1

除了 $s=$AB、BA 以外的字符串都满足条件。

由 ChatGPT 4.1 翻译