/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋くんは、偏りがない 6 面サイコロ 1 個と、10^9 未満の正の整数 R を 1 個持っています。 サイコロを 1 度振ると 1,2,3,4,5,6 のいずれかの整数の目が出ます。 どの整数の目が出るかは同様に確からしく、サイコロを複数回振ったとき、何回目に出た目の値も互いに独立です。
高橋くんは、次の操作を行います。 はじめ、C=0 です。
- サイコロを振り、C の値を 1 増やす。
- これまでに出た目の合計を X とし、X-R が 10^9 の倍数になったら、操作をやめる。
- 1. に戻る。
操作が終了したときの C の期待値を {}\bmod 998244353 で求めてください。
注意
この問題の制約のもとで、C の期待値は既約分数 p/q として表せ、かつ xq \equiv p\pmod{998244353} を満たす整数 x\ (0\leq x\lt998244353) がただひとつ存在することが示せます。 このような x を出力してください。
制約
- 0\lt R\lt10^9
- R は整数
入力
入力は以下の形式で標準入力から与えられる。
R
出力
答えを 1 行で出力せよ。
入力例 1
1
出力例 1
291034221
操作が終了したときの C の期待値はおよそ 833333333.619047619 で、{}\bmod 998244353 では 291034221 です。
入力例 2
720357616
出力例 2
153778832
Score : 600 points
Problem Statement
Takahashi has an unbiased six-sided die and a positive integer R less than 10^9. Each time the die is cast, it shows one of the numbers 1,2,3,4,5,6 with equal probability, independently of the outcomes of the other trials.
Takahashi will perform the following procedure. Initially, C=0.
- Cast the die and increment C by 1.
- Let X be the sum of the numbers shown so far. If X-R is a multiple of 10^9, quit the procedure.
- Go back to step 1.
Find the expected value of C at the end of the procedure, modulo 998244353.
Notes
Under the constraints of this problem, it can be shown that the expected value of C is represented as an irreducible fraction p/q, and there is a unique integer x\ (0\leq x\lt998244353) such that xq \equiv p\pmod{998244353}. Print this x.
Constraints
- 0\lt R\lt10^9
- R is an integer.
Input
The input is given from Standard Input in the following format:
R
Output
Print a single line containing the answer.
Sample Input 1
1
Sample Output 1
291034221
The expected value of C at the end of the procedure is approximately 833333333.619047619, and 291034221 when represented modulo 998244353.
Sample Input 2
720357616
Sample Output 2
153778832