You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

也许我再好一点，我们就不会是这个结果。

core 学长曾经遇到过一位很好很好的学姐。

她会在实验室最冷的深夜，顺手把一杯热奶茶放在还亮着的屏幕旁；会在他榜单失意时说“没关系，下次一定”。她的题解写得比官方还清楚，笑起来的时候，比任何一块奖牌都亮。core 学长很久之后才发现，自己的每一点进步里，都藏着她的影子。

只是最后，他们没能走到一起。没有争吵，也没有像样的告别——就像一段看似无误的代码，在某个毫无征兆的样例上，安静地输出了错误的结果。

回想起这段经历，他意识到自己还有许多不足。于是他决定沉下心来磨炼自己，并为自己设计了一场试炼——如果结局无法重测，那就让过程好一点，再好一点。

题目描述

试炼场地是一条长度为 n 的直线廊道，由 n 个连续格子组成，你需要用能量模块恰好铺满整条廊道。

共有三种能量模块（均可使用任意多次、无编号；一个方案由从左到右放置的模块序列唯一确定）：

• A 模块：占据 1 个格子；
• B 模块：占据 1 个格子；
• C 模块：占据相邻的 2 个格子，不可拆分。

铺满时需满足以下限制：

1. 一个 C 的右侧不能紧接着另一个 C；
2. 与 C 相邻的格子不能放置 B——若一个 C 占据第 l、l+1 格，则当 l > 1 时第 l-1 格、当 l+1 < n 时第 l+2 格不能放置 B（C 自身占据的两格无额外限制）。

换句话说，与 C 相邻的模块（若存在）只能是 A。

铺满长为 n 的廊道有多少种铺法？答案可能很大，请对 998244353 取模。

输入格式

一行一个整数 n，表示廊道长度。

输出格式

一行一个整数，表示合法方案数对 998244353 取模后的结果。

数据范围

对于所有测试数据，满足 1 ≤ n ≤ 1000。

样例

其中样例 2 的五种方案为：AA、AB、BA、BB、C。