/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
すぬけ君は 1 以上 N 以下の整数が等確率で出るサイコロと整数 1 を持っています。
すぬけ君は持っている数が M 以下である間、次の操作を繰り返します。
- サイコロを振り、出た目を x とする。持っている数に x を掛ける。
操作を終了するまでにすぬけ君がサイコロを振った回数の期待値を \text{mod } 10^9+7 で求めてください。
期待値 \pmod{10^9+7} の定義
求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not\equiv 0 \pmod{10^9+7} となることも証明できます。よって、R \times Q \equiv P \pmod{10^9+7}, 0 \leq R \lt 10^9+7 を満たす整数 R が一意に定まります。 この R を答えてください。制約
- 2 \leq N \leq 10^9
- 1 \leq M \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
2 1
出力例 1
2
答えはサイコロで 2 が出るまでにサイコロを振る回数の期待値になります。よって 2 を出力します。
入力例 2
2 39
出力例 2
12
答えはサイコロで 2 が 6 回出るまでにサイコロを振る回数の期待値になります。よって 12 を出力します。
入力例 3
3 2
出力例 3
250000004
答えは \frac{9}{4} です。4 \times 250000004 \equiv 9 \pmod{10^9+7} なので 250000004 を出力します。
\bf{10^9 + 7 = 1000000007} で \mathrm{mod} を取る必要があるのに注意してください。
入力例 4
2392 39239
出力例 4
984914531
入力例 5
1000000000 1000000000
出力例 5
776759630
Score : 600 points
Problem Statement
Snuke has a die (singular of dice) that shows integers from 1 through N with equal probability, and an integer 1.
He repeats the following operation while his integer is less than or equal to M.
- He rolls the die. If the die shows an integer x, he multiplies his integer by x.
Find the expected value of the number of times he rolls the die until he stops, modulo 10^9+7.
Definition of the expected value modulo 10^9+7
We can prove that the desired expected value is always a rational number. Moreover, under the constraints of the problem, when the value is represented as an irreducible fraction \frac{P}{Q}, we can also prove that Q \not\equiv 0 \pmod{10^9+7}. Thus, an integer R such that R \times Q \equiv P \pmod{10^9+7} and 0 \leq R \lt 10^9+7 is uniquely determined. Answer such R.Constraints
- 2 \leq N \leq 10^9
- 1 \leq M \leq 10^9
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 1
Sample Output 1
2
The answer is the expected value of the number of rolls until it shows 2 for the first time. Thus, 2 should be printed.
Sample Input 2
2 39
Sample Output 2
12
The answer is the expected value of the number of rolls until it shows 2 six times. Thus, 12 should be printed.
Sample Input 3
3 2
Sample Output 3
250000004
The answer is \frac{9}{4}. We have 4 \times 250000004 \equiv 9 \pmod{10^9+7}, so 250000004 should be printed.
Note that the answer should be printed modulo \bf{10^9 + 7 = 1000000007}.
Sample Input 4
2392 39239
Sample Output 4
984914531
Sample Input 5
1000000000 1000000000
Sample Output 5
776759630