Unusual Sequences

1000ms

262144K

Description:

Count the number of distinct sequences a₁, a₂, ..., a_n (1 ≤ a_i) consisting of positive integers such that gcd(a₁, a₂, ..., a_n) = x and $\text{[math]}$ . As this number could be large, print the answer modulo 10⁹ + 7.

gcd here means the greatest common divisor.

Input:

The only line contains two positive integers x and y (1 ≤ x, y ≤ 10⁹).

Output:

Print the number of such sequences modulo 10⁹ + 7.

Sample Input:

3 9

Sample Output:

Sample Input:

5 8

Sample Output:

Note:

There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).

There are no suitable sequences in the second test.

Informação

Provedor Codeforces

Código CF900D