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$.

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.

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