题目背景

你怎么知道我新手池十连双金
你怎么知道我星期日单抽出奇迹
你怎么知道我救世主2+1
你怎么知道......

“......谁问你了？”

题目描述

小墨刚刚结束了抽卡。

他可以通过两种方式获取 列车专票 进行跃迁：

• 花费 $160$ 星琼兑换 $1$ 张 列车专票，进行 $1$ 次跃迁（即单次抽卡）。
• 花费 $1600$ 星琼兑换 $10$ 张 列车专票，进行 $10$ 次跃迁（即十次抽卡，简称十连抽）。

小墨有一个固定的抽卡习惯：他不会连续进行两次十连抽。

现在给定小墨本次抽卡所使用的 列车专票 数量，请你计算出小墨本次抽卡中，所有符合上述规则的抽卡过程的 方案数$^{\dagger}$，需对 $998244353$ 取模。

$^{\dagger}$约定 一抽 + 十连 + 一抽 与 一抽 + 一抽 + 十连 为两种 不同 的方案。

输入格式

输入一行一个数字 $n$ $(1 \leq n \leq 3 \times 10^5)$，表示小墨本次抽卡所使用的 列车专票 数。

输出格式

输出一个整数，表示所有符合上述规则的抽卡过程的方案数，对 $998244353$ 取模。

12

4

666

572505039

说明

对于样例 $2$，注意答案很大，你需要取模 $998244353$ 后输出。