Time Limit: 10000 MS Memory Limit: 65536 K
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
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 only one line with the answer modulo 1000000007
7 4 1 1
58 4 1000 47 1000000000 1000
5 1 7322 219736903 666683069