Source: Denso Create Programming Contest 2022 (AtCoder Beginner Contest 239) Ex. 「Dice Product 2」

题目描述

给定两个正整数 $n,m$。

有一个正整数 $M$ ，初始 $M=1$ 。你将进行若干次操作，每次在 $[1,n]$ 中均匀随机选取一个整数 $x$ ，并令 $M:=M\times x$ 。当 $M\ge m$ 时停止操作。

求期望进行多少次操作。

可以证明，答案一定为有理数。设其为 $\frac a b$（$a$ 和 $b$ 为互质的正整数，数据保证 $b$ 不为 $10^9+7$ 的倍数），则你需要输出一个整数 $x$ 满足 $0\le x < 10^9+7$ 且 $a\equiv bx \pmod{10^9+7}$ 。可以证明这样的 $x$ 唯一存在。

输入格式

一行，两个正整数 $n,m$。

输出格式

一行，一个整数 $x$ ，意义同题目描述。

样例

2 1

2

2 39

12

3 2

250000004

答案为 $\frac 9 4$，$4\times 250000004\equiv 9 \pmod{10^9+7}$。

2392 39239

984914531

1000000000 1000000000

776759630

数据范围

对于全部数据，$2\le n\le 10^9$，$1\le m\le 10^9$。