AT_abc300_e [ABC300E] Dice Product 3

[problemUrl]: https://atcoder.jp/contests/abc300/tasks/abc300_e あなたは $ 1 $ 以上 $ 6 $ 以下の整数が等確率で出るサイコロと整数 $ 1 $ を持っています。 あなたは持っている整数が $ N $ 未満である間、次の操作を繰り返します。 - サイコロを振り、出た目を $ x $ とする。持っている整数に $ x $ を掛ける。 全ての操作を終了した時に、持っている整数が $ N $ に一致する確率を $ \text{mod\ }998244353 $ で求めてください。 確率 $ \text{mod\ }998244353 $ とは？ 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、$ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。

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

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

### 制約 - $ 2\ \leq\ N\ \leq\ 10^{18} $ - $ N $ は整数 ### Sample Explanation 1 操作が終了するまでの手順としてあり得る一例を挙げると次のようになります。 - はじめ, 持っている整数は $ 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 $ を出力してください。 ### Sample Explanation 2 どのような目が出ても、操作後に持っている整数が $ 7 $ になることはありません。