骰子点数之和

题目描述

高桥君有一个均匀的六面骰子和一个小于 $10^9$ 的正整数 $R$。 每次掷骰子,都会等概率地显示 $1, 2, 3, 4, 5, 6$ 中的一个数字,且与其它次的结果相互独立。

高桥君将执行以下步骤:

1. 初始时,$C = 0$。
2. 掷骰子,并将 $C$ 增加 $1$。
3. 设到目前为止掷出的数字之和为 $X$。如果 $X - R$ 是 $10^9$ 的倍数,则结束本过程。
4. 返回步骤 2。

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

输入格式

输入按以下格式从标准输入给出:

$R$

输出格式

输出一行答案。

样例

1

291034221

本过程结束时 $C$ 的期望值约为 $833333333.619047619$,对 $998244353$ 取模后为 $291034221$。

720357616

153778832

数据范围

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

提示

在本问题的约束下,可以证明 $C$ 的期望值可以表示为既约分数 $p/q$,并且存在唯一的整数 $x\ (0 \le x \lt 998244353)$ 满足 $xq \equiv p \pmod{998244353}$。输出这个 $x$。