/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
あなたは 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 を求めてください。制約
- 2 \leq N \leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
全ての操作を終了した時に、持っている整数が N に一致する確率を \text{mod }998244353 で出力せよ。
入力例 1
6
出力例 1
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 を出力してください。
入力例 2
7
出力例 2
0
どのような目が出ても、操作後に持っている整数が 7 になることはありません。
入力例 3
300
出力例 3
183676961
入力例 4
979552051200000000
出力例 4
812376310
Score : 500 points
Problem Statement
You have an integer 1 and a die that shows integers between 1 and 6 (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than N:
- Cast a die. If it shows x, multiply your integer by x.
Find the probability, modulo 998244353, that your integer ends up being N.
How to find a probability modulo 998244353?
We can prove that the sought probability is always rational. Additionally, under the constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.Constraints
- 2 \leq N \leq 10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the probability, modulo 998244353, that your integer ends up being N.
Sample Input 1
6
Sample Output 1
239578645
One of the possible procedures is as follows.
- Initially, your integer is 1.
- You cast a die, and it shows 2. Your integer becomes 1 \times 2 = 2.
- You cast a die, and it shows 4. Your integer becomes 2 \times 4 = 8.
- Now your integer is not less than 6, so you terminate the procedure.
Your integer ends up being 8, which is not equal to N = 6.
The probability that your integer ends up being 6 is \frac{7}{25}. Since 239578645 \times 25 \equiv 7 \pmod{998244353}, print 239578645.
Sample Input 2
7
Sample Output 2
0
No matter what the die shows, your integer never ends up being 7.
Sample Input 3
300
Sample Output 3
183676961
Sample Input 4
979552051200000000
Sample Output 4
812376310