Time Limit: 10000 MS Memory Limit: 65536 K

Description

Farmer John had N cows numbered 0 to N-1. One day he saw K cows running away from his farm. Fox Brus
computed the sum of the numbers of the escaped cows. She only told John that the sum was divisible by N.


Your task is to help John by counting the number of possible sets of escaped cows. This number may be very bigŁ¬so modulo 1000000007


Input

The input file will contain one line two numbers N and K,N will be between 1 and 1,000,000,000, inclusive.K will be between 1 and 1,000, inclusive.K will be less than or equal to N.

Output

output only one line with the answer modulo 1000000007

Sample Input

7 4
1 1
58 4 1000 47 1000000000 1000

Sample Output

5
1
7322
219736903
666683069