問題文

高橋くんは、偏りがない $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$ で求めてください。

注意

この問題の制約のもとで、$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