配点 : $500$ 点

問題文

あなたは $1$ 以上 $6$ 以下の整数が等確率で出るサイコロと整数 $1$ を持っています。 あなたは持っている整数が $N$ 未満である間、次の操作を繰り返します。

• サイコロを振り、出た目を $x$ とする。持っている整数に $x$ を掛ける。

全ての操作を終了した時に、持っている整数が $N$ に一致する確率を $\text{mod }998244353$ で求めてください。

制約

• $2 \leq N \leq 10^{18}$
• $N$ は整数

入力

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

$N$

出力

全ての操作を終了した時に、持っている整数が $N$ に一致する確率を $\text{mod }998244353$ で出力せよ。

6

239578645

操作が終了するまでの手順としてあり得る一例を挙げると次のようになります。

• はじめ, 持っている整数は $1$ である。
• サイコロを振り, $2$ が出る。持っている整数は $1 \times 2 = 2$ になる。
• サイコロを振り, $4$ が出る。持っている整数は $2 \times 4 = 8$ になる。
• 持っている整数が $6$ 以上になったので操作を終了する。

操作がこのように進んだ場合、操作後に持っている整数は $8$ であり $N = 6$ に一致しません。

操作後に持っている整数が $6$ である確率は $\frac{7}{25}$ です。 $239578645 \times 25 \equiv 7 \pmod{998244353}$ より、 $239578645$ を出力してください。

7

0

どのような目が出ても、操作後に持っている整数が $7$ になることはありません。

300

183676961

979552051200000000

812376310