← 返回题目列表

AtCoder · abc299_h

Ex. 骰子总和无穷大

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥有一个无偏六面骰子和一个正整数 R 小于 10^9。 每次掷骰子时,都会显示其中一个数字 1,2,3,4,5,6 具有相同的概率,独立于其他试验的结果。

Takahashi 将执行以下程序。 最初, C=0.

  1. 掷骰子并增量 C by 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,和 291034221 当表示模数时 998244353.


示例输入 2

720357616

示例输出 2

153778832