分数: 600 点
问题陈述
高桥有一个无偏六面骰子和一个正整数 R 小于 10^9。 每次掷骰子时,都会显示其中一个数字 1,2,3,4,5,6 具有相同的概率,独立于其他试验的结果。
Takahashi 将执行以下程序。 最初, C=0.
- 掷骰子并增量 C by 1.
- 让 X 是迄今为止显示的数字的总和。如果 X-R 是的倍数 10^9,退出程序。
- 返回步骤 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,和 291034221 当表示模数时 998244353.
示例输入 2
720357616
示例输出 2
153778832