#C. Unusual Sequences

    远端评测题 1000ms 256MiB

Unusual Sequences

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Count the number of distinct sequences a1, a2, ..., an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, ..., an) = x and . As this number could be large, print the answer modulo 109 + 7.

gcd here means the greatest common divisor.

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

Print the number of such sequences modulo 109 + 7.

Input

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

Output

Print the number of such sequences modulo 109 + 7.

3 9

5 8

3

0

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.

2024暑期集训第五周小测

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2024-7-31 19:00
结束于
2024-7-31 21:00
持续时间
2 小时
主持人
参赛人数
33