AT_abc299_h [ABC299Ex] Dice Sum Infinity

题目描述

高桥君有一个没有偏差的 $6$ 面骰子和一个小于 $10^9$ 的正整数 $R$。每次掷骰子时，会出现 $1,2,3,4,5,6$ 中的某一个整数点数。每个点数出现的概率相同，且多次掷骰子的结果相互独立。

高桥君进行如下操作。初始时，$C=0$。

1. 掷骰子一次，将 $C$ 的值加 $1$。
2. 设到目前为止所有掷出的点数之和为 $X$，如果 $X-R$ 是 $10^9$ 的倍数，则停止操作。
3. 否则，回到步骤 1。

请你求出操作结束时 $C$ 的期望值，并将答案对 $998244353$ 取模后输出。

输入格式

输入为一行，包含一个整数 $R$。

输出格式

输出一行，表示答案。

输入输出样例 #1

输入 #1

1

输出 #1

291034221

输入输出样例 #2

输入 #2

720357616

输出 #2

153778832

说明/提示

注意

在本题的约束下，$C$ 的期望值可以表示为最简分数 $p/q$，且存在唯一的整数 $x$（$0\leq x<998244353$），满足 $xq\equiv p\pmod{998244353}$。请输出这样的 $x$。

约束条件

• $0<R<10^9$
• $R$ 是整数

样例解释 1

操作结束时 $C$ 的期望值大约为 $833333333.619047619$，对 $998244353$ 取模后为 $291034221$。

由 ChatGPT 4.1 翻译