Shil and weird equation (Optional)

3.9

134 votes
Medium
Problem

Shil came across a weird equation and he wants to find out total number of solutions of this equation.The weird equation is :
x1+ x2 + x3 ... xN = D .
Find total number of solutions of this equation such that each xi are non-negative and gcd of all the xi is one.Here gcd stands for greatest common divisor.
Assume that gcd(0,y) = y for any y.

Input:
Only line of input consists of two integers N and D .

Output:
Output total number of solutions modulus 109+7

Constraint:
1 ≤ N ≤ 104
1 ≤ D ≤ 104

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

All the possible cases are:
1.) x1=1 , x2=0 , x3=1
2.) x1=1 , x2=1 , x3=0
3.) x1=0 , x2=1 , x3=1

Editor Image

?