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 $\sum_{i = 1}^{n} a_{i} = y$. As this number could be large, print the answer modulo 10^9 + 7.

gcd here means the greatest common divisor.


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
3 9

Output
3

Input
5 8

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

Difficulty: interview

Starter code:

Solutions:
import sys

x,y = list(map(int, input().strip().split()))

if y % x != 0:
    print(0)
    return

MOD = 10**9 + 7

K = y//x

def multiply(A,b, MOD):
    n, m = len(A), len(b[0])
    matrika = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            vsota = 0
            for k in range(len(A[0])):
                vsota += A[i][k]*b[k][j]
            matrika[i][j] = vsota % MOD
    return matrika

def copy(mat):
    return [e[:] for e in mat]

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    matrika = [[1,1],[1,0]]

    pripravi = dict()
    pripravi[1] = copy(matrika)
    s = 1

    pot = [1]

    working = copy(matrika)
    
    while s <= n:
        working = multiply(working,working,MOD)
        s*= 2
        pripravi[s] = copy(working)
        pot.append(s)

    manjka = n-2
    pointer = len(pot) - 1
    while manjka > 0:
        if pot[pointer] > manjka:
            pointer -= 1
        else:
            matrika = multiply(matrika, pripravi[pot[pointer]], MOD)
            manjka -= pot[pointer]

    v = [[1],[0]]

    return multiply(matrika, v, MOD)[0][0]

memo2 = dict()
def find(y):
    if y in memo2:
        return memo2[y]
    ALL = (pow(2, y - 1, MOD)) % MOD

    k = 2
    while k*k <= y:
        if y % k == 0:
            if k*k != y:
                ALL -= find(y//k)
                ALL -= find(k)
            else:
                ALL -= find(k)
        k += 1
        #print(k, ALL)

    if y != 1:
        ALL -= 1

    memo2[y] = ALL % MOD
    return ALL % MOD

print(find(K) % MOD)


def gcd(x,y):
    if x == 0:
        return y
    if y > x:
        return gcd(y,x)
    if x % y == 0:
        return y
    return gcd(y, x % y)


memo = dict()
def brute(k, gc):
    if (k,gc) in memo:
        return memo[k,gc]
    if k == 0:
        if gc:
            return 1
        else:
            return 0
    ALL = 0
    for i in range(1, k + 1):
        ALL += brute(k-i,gcd(gc,i))
    memo[k, gc] = ALL
    return ALL

#print(brute(K,0) % MOD)
            


mod = 1000000007
def modpow(a, x):
	if x==0:
		return 1
	if x==1:
		return a
	b = modpow(a, x//2)
	return (b*b*(a ** (x%2))) % mod


import sys
x,y = list(map(int, input().split()))
if y%x != 0:
	print(0)
	return
if x==y:
	print(1)
	return	

a = y//x

divs = []

i=2
while i*i < a:
	if a%i == 0:
		divs.append(i)
		divs.append(a//i)
	i+=1
		
if int(a ** 0.5) **2 == a:
	divs.append(int(a**0.5))

divs.append(a)

divs.sort()

#print(divs)
		
res = modpow(2, a-1)
muls = [0 for _ in divs]
muls[0] = 1;

for xid,d in enumerate(divs):
	prevs = 0
	for id,d2 in enumerate(divs):
		if d2<d and d%d2 == 0:
			prevs+=muls[id]
	muls[xid] = (1-prevs)
	res += (prevs-1) * modpow(2, a//d - 1)
	
	res = (res + 1000 * mod) % mod
	#print(d, res, ',', prevs)
	
#print(muls)
print(res)




mod = 1000000007
def modpow(a, x):
	if x==0:
		return 1
	if x==1:
		return a
	b = modpow(a, x//2)
	return (b*b*(a ** (x%2))) % mod


import sys
x,y = list(map(int, input().split()))
if y%x != 0:
	print(0)
	return
if x==y:
	print(1)
	return	

a = y//x

divs = []

i=2
while i*i < a:
	if a%i == 0:
		divs.append(i)
		divs.append(a//i)
	i+=1
		
if int(a ** 0.5) **2 == a:
	divs.append(int(a**0.5))

divs.append(a)

divs.sort()

#print(divs)
		
res = modpow(2, a-1)
muls = [0 for _ in divs]
muls[0] = 1;

for xid,d in enumerate(divs):
	prevs = 0
	for id,d2 in enumerate(divs):
		if d2<d and d%d2 == 0:
			prevs+=muls[id]
	muls[xid] = (1-prevs)
	res += (prevs-1) * modpow(2, a//d - 1)
	
	res = (res + 1000 * mod) % mod
	#print(d, res, ',', prevs)
	
#print(muls)
print(res)

'''
midpow function copy marsi.
39 no line thaki 51 copy marsi.
tou kita oiche
as if i care
'''


import sys
mod = 1000000007
def modpow(a, x):
    if x == 0:
        return 1
    if x == 1:
        return a
    b = modpow(a, x//2)
    return (b*b*(a ** (x%2))) % mod


n,m = list(map(int, input().split()))
#ans = gcd(n,m)
if m%n != 0:
    print(0)
    return
if n == m:
    print(1)
    return
ans = m//n
arr = []
i = 2
while i*i < ans:
    if ans%i == 0:
        arr.append(i)
        arr.append(ans//i)
    i += 1
if int(ans ** 0.5) ** 2 == ans:
    arr.append(int(ans** 0.5))
arr.append(ans)
arr.sort()
result  = modpow(2, ans -1)
muls = [0 for _ in arr]
muls[0] = 1
for xid,d in enumerate(arr):
    prevs = 0
    for id,d2 in enumerate(arr):
        if d2 < d and d%d2 ==0:
            prevs += muls[id]
    muls[xid] = (1 - prevs)
    result += (prevs - 1) * modpow(2, ans//d - 1)

    result = (result + 1000 * mod) % mod
print(result)


import operator, math, itertools, functools
mod = int(1e9 + 7)

def factor(n):
	a = []
	for i in range(2, int(math.sqrt(n))+1):
		while n % i == 0:
			a.append(i)
			n //= i
	if n > 1: a.append(n)
	return a
	
def comp(n):
	f = set(factor(n))
	c = pow(2, n-1, mod)
	for i in range(1, len(f)+1):
		if i & 1:
			sign = -1
		else:
			sign = 1
		for j in itertools.combinations(f, i):
			k = functools.reduce(operator.mul, j)
			c += sign * pow(2, n//k-1, mod)
			c = c % mod
	return c		
	
x, y = map(int, input().split())
if y % x == 0:
	print(comp(y // x))
else:
	print(0)

#!/usr/bin/env python3

from fractions import gcd
from operator import mul
from functools import reduce
from itertools import combinations


eval_function = lambda x: lambda f: f(x)


@eval_function(int((10**9)**0.5))
def prime(n):
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    index = 2
    for i in range(int(len(sieve)**0.5)):
        if sieve[i]:
            for j in range(2*i, len(sieve), i):
                sieve[j] = False
        index += 1
    return [i for i, is_prime in enumerate(sieve) if is_prime]


def factorized(n):
    factors = []
    for i in prime:
        if i**2 > n:
            break
        while not n % i:
            factors += [i]
            n //= i
    if n > 1:
        factors += [n]
    return factors


def solve(x, y, mod=None):
    if gcd(x, y) != x:
        return 0
    y = y//x
    c = pow(2, y-1, mod)
    unique_factors = set(factorized(y))
    for i in range(1, len(unique_factors)+1):
        for divisor in combinations(unique_factors, i):
            d = reduce(mul, divisor)
            c += (-1)**i * pow(2, y//d-1, mod)
            c %= mod
    return c


def main():
    x, y = [int(n) for n in input().split()]
    print(solve(x, y, 10**9+7))


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3

from fractions import gcd
from operator import mul
from functools import reduce
from itertools import combinations


eval_function = lambda x: lambda f: f(x)


@eval_function(int((10**9)**0.5))
def prime(n):
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    index = 2
    for i in range(int(len(sieve)**0.5)):
        if sieve[i]:
            for j in range(2*i, len(sieve), i):
                sieve[j] = False
        index += 1
    return [i for i, is_prime in enumerate(sieve) if is_prime]


def factorized(n):
    factors = []
    for i in prime:
        if i**2 > n:
            break
        while n % i == 0:
            factors += [i]
            n //= i
    if n > 1:
        factors += [n]
    return factors


def count_coprime_parts(n, mod=None):
    count = pow(2, n-1, mod)
    unique_factors = set(factorized(n))
    for i in range(1, len(unique_factors)+1):
        for factors in combinations(unique_factors, i):
            d = reduce(mul, factors)
            count += (-1)**i * pow(2, n//d-1, mod)
            count %= mod
    return count


def solve(x, y, mod=None):
    if gcd(x, y) != x:
        return 0
    return count_coprime_parts(y//x, mod)


def main():
    x, y = [int(n) for n in input().split()]
    print(solve(x, y, 10**9+7))


def __starting_point():
    main()

__starting_point()

M=10**9+7
a,b=list(map(int,input().split()))
if b%a:print(0)
else:
    b//=a
    d=set()
    for i in range(1,int(pow(b,0.5)+1)):
        if b%i==0:
            d.add(i)
            d.add(b//i)
    d=sorted(list(d))
    f=d[::]
    for i in range(len(f)):
        f[i]=pow(2,d[i]-1,M)
        for j in range(i):
            if d[i]%d[j]==0:
                f[i]-=f[j]
    print(f[-1]%M)


M=10**9+7
a,b=map(int,input().split())
if b%a:print(0)
else:
    b//=a
    d=set()
    for i in range(1,int(pow(b,0.5)+1)):
        if b%i==0:
            d.add(i)
            d.add(b//i)
    d=sorted(list(d))
    f=d[::]
    for i in range(len(f)):
        f[i]=pow(2,d[i]-1,M)
        for j in range(i):
            if d[i]%d[j]==0:
                f[i]-=f[j]
    print(f[-1]%M)

x, y = map(int, input().split())
b = y // x
if y % x != 0:
    print(0);return
ds = set()
M = 10**9 + 7
for i in range(1, int(pow(b,0.5)+1)):
    if b % i == 0:
        ds.add(i)
        ds.add(b//i)
ds = sorted(list(ds))
ans = pow(2, b-1, M)
f = ds[::]
for i in range(len(ds)):
    f[i] = pow(2, ds[i]-1, M)
    for j in range(i):
        if ds[i] % ds[j] == 0:
            f[i] -= f[j]
print(f[-1]%M)

def bin_pow(num, degree , module):
    if degree == 0:
        return 1
    if degree == 1:
        return num % module

    if degree % 2 == 0:
        val = bin_pow(num, degree // 2, module)
        return (val * val) % module
    
    return (num * bin_pow(num , degree - 1, module)) % module



x, y = list(map(int,input().split()))


if y % x != 0:
    print(0)
    return

y //= x

divs = set()
to_gen = []

num = 2
val = y

while num * num <= val:
    degree = 0
    while y % num == 0:
        degree+=1
        y //= num
    if degree != 0:
        to_gen.append((num, degree))

    if num == 2:
        num += 1
    else:
        num += 2

if y != 1:
    to_gen.append((y, 1))

    
to_gen_len = len(to_gen)

def generate(ind):
    if ind == to_gen_len:
        yield 1
        return 
    gen_val = to_gen[ind][0]
    
    for deg in range(1 + to_gen[ind][1]):
        for each in generate(ind  + 1):
            yield gen_val**deg * each

for each in generate(0):
    divs.add(each)

divs = list(divs)
divs.sort()
divs_answers = {}
mod = 10**9 + 7
ans = bin_pow(2, val - 1, mod)

for el in divs:
    if el == 1:
        divs_answers[el] = 1
        ans -= 1
    else:
        curr_val = bin_pow(2, el - 1 ,mod)
        for other_el in divs:
            if other_el >= el:
                break
            if el % other_el !=0:
                continue
            
            curr_val -= divs_answers[other_el]

        divs_answers[el] = curr_val % mod
        ans -= curr_val

print(divs_answers[val])



mod=10**9+7
num1,num2=list(map(int,input().split()))
if num2%num1:
	print("0")
else:
    num2=num2//num1
    arr=set()
    for i in range(1,int(pow(num2,0.5)+1)):
        if num2%i==0:
            arr.add(i)
            arr.add(num2//i)
    arr=sorted(list(arr))
    cop2=arr[::]
    for i in range(len(cop2)):
        cop2[i]=pow(2,arr[i]-1,mod)
        for j in range(i):
            if arr[i]%arr[j]==0:
                cop2[i]-=cop2[j]
    print(cop2[-1]%mod)



MOD = 1000000007

x, y = map(int,input().split())

if y%x == 0: # 'y' must be divisible by 'x'
    div = y // x
    y_mult = set() # Distinc common multiples for y
    for i in range(1, int(pow(div, 0.5) + 1)): # Just is neccesary until root of div
        if div % i == 0:
            y_mult.add(i)
            y_mult.add(div // i)
    y_mult = sorted(list(y_mult))
    ym_copy = y_mult.copy()
    for i in range(len(ym_copy)):
        ym_copy[i] = pow(2, y_mult[i]-1, MOD) # Efficient pow 
        for j in range(i):
            if y_mult[i]%y_mult[j] == 0:
                ym_copy[i] -= ym_copy[j]
    print(ym_copy[-1]%MOD)
else:
    print(0)


modulo=10**9+7
num1,num2=list(map(int,input().split()))
if num2%num1:
	print("0")
else:
    num2=num2//num1
    arr=set()
    for i in range(1,int(pow(num2,0.5)+1)):
        if num2%i==0:
            arr.add(i)
            arr.add(num2//i)
    arr=sorted(list(arr))
    cop2=arr[::]
    for i in range(len(cop2)):
        cop2[i]=pow(2,arr[i]-1,modulo)
        for j in range(i):
            if arr[i]%arr[j]==0:
                cop2[i]-=cop2[j]
    print(cop2[-1]%modulo)




# coding: utf-8

# In[36]:


import math

def UnusualSeq(a,b):
    if b%a!=0:
        print(0)
    else:
        b//=a
        d=set()
        for i in range(1,int(math.sqrt(b)+1)):
            if b%i==0:
                d.add(i)
                d.add(b//i)
        d=sorted(list(d))
        f=d[::]
        for i in range(len(f)):
            f[i]=pow(2,d[i]-1,(10**9+7))
            for j in range(i):
                if d[i]%d[j]==0:
                    f[i]-=f[j]
        print(f[-1]%(10**9+7))


a,b=list(map(int,input().split()))
UnusualSeq(a,b)



M=10**9+7
a,b=map(int,input().split())
if b%a:print(0)
else:
    b//=a
    d=set()
    for i in range(1,int(pow(b,0.5)+1)):
        if b%i==0:
            d.add(i)
            d.add(b//i)
    d=sorted(list(d))
    f=d[::]
    for i in range(len(f)):
        f[i]=pow(2,d[i]-1,M)
        for j in range(i):
            if d[i]%d[j]==0:
                f[i]-=f[j]
    print(f[-1]%M)

import math
lectura=lambda:map (int,input().split())
x,y=lectura()
mod= 1000000007
if (y%x!=0):
    print("0")
else:
    y= y//x
    setPrueba=set()
    for i in range(1, int(math.sqrt(y) + 1)):
        if (y%i==0):
            setPrueba.add(i)
            setPrueba.add(y// i)
    setPrueba=sorted(list(setPrueba))
    setOrdenado= setPrueba.copy()
    for i in range(len(setOrdenado)):
        #setOrdenado[i] = math.pow(2, setPrueba[i] - 1)
        setOrdenado[i]=pow(2, setPrueba[i] - 1, mod)
        for j in range(i):
            if setPrueba[i]% setPrueba[j]==0:
                setOrdenado[i]-= setOrdenado[j]
    print(setOrdenado[len(setOrdenado)-1] % mod)

import math

mod= 1000000007

x, y = [int(x) for x in input().split()]

if y%x != 0:
    print(0)
    return
 
y= y//x
seqs=set()	

for x in range(1, int(math.sqrt(y) + 1)):
	if y%x != 0:
		continue
	seqs.add(x)
	seqs.add(y// x)

seqs=sorted(list(seqs))
ordered= seqs.copy()

for i in range(len(seqs)):
	ordered[i]=pow(2, seqs[i] - 1, mod)
	for j in range(i):
		if seqs[i]% seqs[j] == 0:
			ordered[i]-= ordered[j]
print(int(ordered[len(ordered)-1] % mod))


p=1000000007
def mul(x,y):
    rt=1
    while y>0:
        if y%2==1:
            rt=(rt*x)%p
        x=(x*x)%p
        y=y//2
    return rt
 
x,y=list(map(int,input().split()))
if(y%x!=0):print(0)
else:
    y/=x
    d=set([])
    i=1
    while i*i<=y:
        if y%i==0:
            d.add(i);d.add(y/i)
        i+=1
    d=sorted(list(d))
    dp=d[::]
    for i in range(len(d)):
        dp[i]=mul(2,d[i]-1)
        for j in range(i):
            if d[i]%d[j]==0:
                dp[i]-=dp[j]
    print(dp[-1]%p)


import sys
mod = 1000000007
def mul(x,y):
    res=1
    while y>0:
        if y%2==1:
            res=(res*x)%mod
        x=(x*x)%mod
        y//=2
    return res
x,y = list(map(int,sys.stdin.readline().split()))
if(y%x!=0):
    print(0)
else:
    y/=x
    d=set([])
    i=1
    while i*i<=y:
        if y%i==0:
            d.add(i);d.add(y/i)
        i+=1
    d=sorted(list(d))
    dp=d[::]
    for i in range(len(d)):
        dp[i]=mul(2,d[i]-1)
        for j in range(i):
            if d[i]%d[j]==0:
                dp[i]-=dp[j]
    print(dp[-1]%mod)



from collections import defaultdict
x, y = map(int, input().split())
if y%x != 0: 
	print(0)
	return
x = y//x
divisors = []
for i in range(1,int(x**(.5))+1):
	if x%i == 0:
		divisors.append(i)
		divisors.append(x//i)
if divisors[-1] == divisors[-2]: divisors.pop()
divisors.sort()
va = defaultdict(int)
va[1] = 1
mod = 10**9 + 7
for i in range(1, len(divisors)):
	k = divisors[i]
	count = pow(2,k-1,mod)
	for j in range(i):
		if k%divisors[j] == 0: count = (count-va[divisors[j]])%mod
	va[k] = count
print(va[x])