Informatica Online Judge

  사기꾼 민제 [2408 / 0968]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 12


The Champion of this Problem (C++) : gs18103 - ms / 801byte
My Best Submission (C++) : N/A

[35th 김병국]
Writer ID : [gs17016]

Background

민제는 노트북을 사고 싶어 열심히 나무를 팔고 있었다.

그러나 나무를 팔아 얻는 보수가 생각보다 적다고 판단한 민제는 나무꾼에서 사기꾼으로 전업했다.

선량한 청주 시민들에게 사기를 치기로 결심한 민제는 어떻게 하면 성공적으로 사기를 칠 수 있을지 2년 11개월 동안 연구하여 엄청난 사실을 알아낼 수 있었다.

바로 민제가 각각의 청주 시민들에게 사기를 쳐서 얻은 금액들의 최대공약수가 정확히 x라면 경찰에게 걸리지 않는다는 것이다!

가격이 y원인 노트북을 사고 싶은 민제는 사기를 쳐서 정확하게 y원의 금액을 벌기로 결심하였다.

민제가 성공적으로 사기를 칠 수 있는 방법의 수를 구해보자. (단, 방법의 수가 너무 클 수도 있으므로 1000000007으로 나눈 나머지를 출력하여라)

Input

두 정수 x, y가 주어진다. (1 <= x, y <= 1000000000)

Output

민제가 성공적으로 사기를 칠 수 있는 방법의 수를 1000000007로 나눈 나머지를 출력한다.

IO Example

입력1
3 9

출력1
3

입력2
5 8

출력2
0

설명
첫번째 입력에서는 (3, 3, 3), (3, 6), (6, 3)으로 3가지 경우가 있다.
두번째 입력에서는 가능한 방법이 존재하지 않는다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]