Gheyme


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Shengdebao has recently created a bank account, and being a cautious fellow, he wants to make sure of the bank's security policies.

Financial experts have come up with a new formula to calculate the amount of security in a bank account. They introduce the amount of security as a quantity represented by a number, this number is calculated as follows:

If a bank has nn doors and kk seats this value is equal to the number of ways to choose kk distinct numbers from 11 to nn so that if we write the pairwise difference between any two (the difference between numbers aa and bb is expressed as ab|a-b|) values (which will be exactly k×(k1)2\frac{k \times (k-1)}{2} values), the gcd (greatest common divisor) of every pair of these k×(k1)2\frac{k \times (k-1)}{2} integers will be 11 or in other words these values must be pairwise coprime!

Shengdebao was quite surprised by the formula and could not find the relevency between this and the security, but who is he to question the experts! So he started counting the number of doors and seats in his bank.

Given the number of doors and seats, help him calculate the amount of security in his bank account.

ورودی🔗

In the only line of input the values nn (number of doors) and kk (the number of seats) are given in the same order.

1n,k2 000 1 \le n , k \le 2\ 000

خروجی🔗

Output only one line the security of the bank. Since the number can be quite large output it modulo 109+710^9 + 7.

مثال🔗

ورودی نمونه ۱🔗

4 4
Plain text

خروجی نمونه ۱🔗

0
Plain text

ورودی نمونه ۲🔗

4 3
Plain text

خروجی نمونه ۲🔗

4
Plain text

Explanation: In this test if we choose three distinct numbers in anyway the conditions will be satisfied.

For example by choosing 1 , 2 and 4 the differences will be equal to 1 , 2 and 3 which are pairwise coprime.

ورودی نمونه ۳🔗

5 2
Plain text

خروجی نمونه ۳🔗

10
Plain text

Explanation: Any pair of numbers chosen will only make exactly one difference which satisfies the criteria.