102397: [AtCoder]ABC239 Ex - Dice Product 2
Description
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
Input
题意翻译
[芷萱姐姐](https://www.luogu.com.cn/user/208653)有一个骰子（单数的骰子），上面写着 $1$ 到 $N$ 的整数，每个整数被骰到的概率是相同的。 现在她有一个整数 $x$，初始为 $1$，每次她都把 $x$ 乘以骰到的数，直到 $x>M$ 为止。现在她想让你求出她操作次数的期望值，对 $10^9+7$ 取模。 + $2 \le N \le 10^9$ + $1 \le M \le 10^9$ Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)Output
问题描述
Snuke有一个骰子，上面等概率地显示着1到N的整数，以及一个整数1。
- 他掷骰子。如果骰子显示的整数为x，他将他的整数乘以x。
求他在停止之前掷骰子的次数的期望值，对10^9+7取模。
对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之前掷骰子的次数的期望值。因此，应该输出12。
样例输入3
3 2
样例输出3
250000004
答案是$\frac{9}{4}$。我们有$4 \times 250000004 \equiv 9 \pmod{10^9+7}$，所以应该输出250000004。
注意答案应该对$\bf{10^9 + 7 = 1000000007}$取模。
样例输入4
2392 39239
样例输出4
984914531
样例输入5
1000000000 1000000000
样例输出5
776759630