Score : $600$ points

问题描述

Snuke 拥有一枚骰子（dice 的单数形式），该骰子以相等的概率显示出从 $1$ 到 $N$ 的整数，同时他还拥有一个整数 $1$。
在满足他的整数小于等于 $M$ 的条件下，他重复执行以下操作：

• 他投掷骰子。如果骰子显示的数字为 $x$，则将他的整数乘以 $x$。

求当他停止时，投掷骰子次数的期望值对 $10^9+7$ 取模的结果。

模 $10^9+7$ 下期望值定义

我们可以证明所求期望值始终是一个有理数。此外，在本题的约束条件下，若期望值表示为不可约分数 $\frac{P}{Q}$，我们还可以证明 $Q \not\equiv 0 \pmod{10^9+7}$。因此，存在一个唯一确定的整数 $R$，满足 $R \times Q \equiv P \pmod{10^9+7}$ 且 $0 \leq R \lt 10^9+7$。请输出这样的 $R$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:20:17