测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A11374. Unusual Sequences

编程题 普及/提高-

题目描述

Count the number of distinct sequences $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}$ ) consisting of positive integers such that $gcd(a_{1},a_{2},...,a_{n})=x$ and ![](/uploads/acgo/image/24869f51f51af6e5_083137ff8122.jpeg). As this number could be large, print the answer modulo $10^{9}+7$ .

$gcd$ here means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).

输入格式

The only line contains two positive integers $x$ and $y$ ( $1<=x,y<=10^{9}$ ).

输出格式

Print the number of such sequences modulo $10^{9}+7$ .

输入输出样例

输入 #1
3 9
输出 #1
3
输入 #2
5 8
输出 #2
0

说明/提示

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.
上一题 去做题 下一题