题目描述

给定一个正偶数 $N$。

找到长度为 $N$ 的由 A、B 和 C 组成的字符串 $s$ 的数量，满足以下条件：

• $s$ 可以通过重复以下操作转化为空字符串：
  • 在 $s$ 中选择两个相邻的字符并删除它们。但是不允许选择 AB 或 BA。

例如，对于 $N=4$，ABBC 满足条件，因为我们可以按如下方式将其转化：ABBC → (删除 BB) → AC → (删除 AC) → (空)。

答案可能很大，因此计算结果对 $998244353$ 取模。

约束条件

• $2 \leq N \leq 10^7$
• $N$ 是一个正偶数。

输入

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

$N$

输出

打印满足条件的字符串的数量，对 $998244353$ 取模。

示例输入 1

2

示例输出 1

7

除了 AB 和 BA，所有可能的字符串都满足条件。

示例输入 2

10

示例输出 2

50007

示例输入 3

1000000

示例输出 3

210055358