← 返回题目列表

Codeforces · 900/D

D. 不寻常的序列

中文机器翻译题面 查看原题

计算由正整数组成的不同序列 a1, a2, ..., an (1 ≤ ai) 的数量,使得 gcd(a1, a2, ..., an) = x 且 $$\sum_{i=1}^{n}a_{i}=y$$。由于这个数字可能很大,因此打印答案模 109 + 7。

这里的gcd是指最大公约数。

输入

唯一一行包含两个正整数 x 和 y (1 ≤ x, y ≤ 109)。

输出

打印以 109 + 7 为模的此类序列的数量。

示例

输入 #1

3 9

输出 #1

3

输入 #2

5 8

输出 #2

0

注意

第一个测试中有三个合适的序列:(3, 3, 3)、(3, 6)、(6, 3)。

第二次测试中没有合适的序列。