← 返回题目列表

AtCoder · agc040_c

C. AB 和 BA 都不是

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是正偶数 N.

查找字符串的数量 重复以下操作即可将 s 长度 N 组成 A, B,和 C 满足以下条件:

  • s 转换为空字符串:
    • 选择两个连续的字符 s 并删除它们。然而,选择 不允许 AB or BA 。

例如, 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