AT_abc239_h [ABC239Ex] Dice Product 2

题目描述

すぬけ君有一个能等概率掷出 $1$ 到 $N$ 的骰子，以及一个整数 $1$。
只要他手中的数不超过 $M$，他就会重复以下操作：

• 掷骰子，记掷出的点数为 $x$，然后将手中的数乘以 $x$。

请你求出，在操作结束前，すぬけ君掷骰子的次数的期望值，并对 $10^9+7$ 取模。

期望值 $\pmod{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 < 10^9+7$。请输出这个 $R$。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 1

输出 #1

2

输入输出样例 #2

输入 #2

2 39

输出 #2

12

输入输出样例 #3

输入 #3

3 2

输出 #3

250000004

输入输出样例 #4

输入 #4

2392 39239

输出 #4

984914531

输入输出样例 #5

输入 #5

1000000000 1000000000

输出 #5

776759630

说明/提示

约束

• $2 \leq N \leq 10^9$
• $1 \leq M \leq 10^9$

样例解释 1

答案是掷出 $2$ 之前掷骰子的期望次数。因此输出 $2$。

样例解释 2

答案是掷出 $2$ 共 $6$ 次之前掷骰子的期望次数。因此输出 $12$。

样例解释 3

答案是 $\frac{9}{4}$。$4 \times 250000004 \equiv 9 \pmod{10^9+7}$，所以输出 $250000004$。
请注意需要对 $10^9+7=1000000007$ 取模。

由 ChatGPT 4.1 翻译