题目描述

高橋くんは、偏りがない $6$ 面サイコロ $1$ 個と、$10^9$ 未満の正の整数 $R$ を $1$ 個持っています。 サイコロを $1$ 度振ると $1,2,3,4,5,6$ のいずれかの整数の目が出ます。 どの整数の目が出るかは同様に確からしく、サイコロを複数回振ったとき、何回目に出た目の値も互いに独立です。

高橋くんは、次の操作を行います。 はじめ、$C=0$ です。

1. サイコロを振り、$C$ の値を $1$ 増やす。
2. これまでに出た目の合計を $X$ とし、$X-R$ が $10^9$ の倍数になったら、操作をやめる。
3. 1. に戻る。

操作が終了したときの $C$ の期待値を ${}\bmod\ 998244353$ で求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$R$

输出格式

答えを $1$ 行で出力せよ。

题目大意

高桥有一个小于 $10^9$ 的正整数 $R$ 和一个质地均匀的正方体骰子，每次掷出骰子都会等概率掷出 $1,2,3,4,5,6$ 中的一个数，且每次掷骰子互不影响。

设 $X$ 为当前掷出的数的总和。高桥将会不断地掷骰子，直到当前 $X-R$ 为 $10^9$ 的倍数时停止。

求掷骰子次数 $C$ 的期望，对 $998244353$ 取余。

具体地，设结果可以表示为既约分数 $\dfrac pq$ 的形式，则输出满足 $xq\equiv p\pmod{998244353}$ 的 $x$，其中 $0\le x<998244353$。可以证明 $x$ 是唯一的。

1

291034221

720357616

153778832

提示

注意

この問題の制約のもとで、$C$ の期待値は既約分数 $p/q$ として表せ、かつ $xq\ \equiv\ p\pmod{998244353}$ を満たす整数 $x\ (0\leq\ x\lt998244353)$ がただひとつ存在することが示せます。 このような $x$ を出力してください。

制約

• $0\lt\ R\lt10^9$
• $R$ は整数

Sample Explanation 1

操作が終了したときの $C$ の期待値はおよそ $833333333.619047619$ で、${}\bmod\ 998244353$ では $291034221$ です。