Ex - Dice Product 2
当前没有测试数据。
Ex - Dice Product 2
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 , we can also prove that . Thus, an integer such that and is uniquely determined. Answer such .
Constraints
- $2 \leq N \leq 10^9$
- $1 \leq M \leq 10^9$
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
2 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.
2 39
12
The answer is the expected value of the number of rolls until it shows $2$ six times. Thus, $12$ should be printed.
3 2
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}$.
2392 39239
984914531
1000000000 1000000000
776759630