题目描述

Takahashi有一个均匀的六面骰子和一个小于 $10^9$ 的正整数 $R$。每次掷骰子，都会以相等的概率出现数字 $1,2,3,4,5,6$，与其他试验结果独立。

Takahashi将执行以下步骤。初始时，$C=0$。

1. 投掷骰子，并将 $C$ 增加 $1$。
2. 令 $X$ 为至今为止出现的数字之和。如果 $X-R$ 是 $10^9$ 的倍数，则中止该过程。
3. 返回到步骤 1。

求过程结束时 $C$ 的期望值，对 $998244353$ 取模。

提示

在问题的约束下，可以证明 $C$ 的期望值表示为不可约分数 $p/q$，并且存在唯一的整数 $x\\ (0\\leq x\\lt998244353)$，使得 $xq \\equiv p\\pmod{998244353}$。输出这个 $x$。

约束条件

• $0\\lt R\\lt10^9$
• $R$ 是整数。

输入

输入以以下格式从标准输入给出：

$R$

输出

输出一行，包含答案。

示例输入1

1

示例输出1

291034221

过程结束时，$C$ 的期望值约为 $833333333.619047619$，当以 $998244353$ 为模表示时为 $291034221$。

示例输入2

720357616

示例输出2

153778832