Tenali Ramakrishna, who was known as Vikatakavi (jester poet) was a Telugu poet generally known for his wit and humor. He joined the famous troupe of 'Bhagavatha Mela'. When the troupe came to Vijayanagara to perform in front of the king, Ramakrishna's performance caught the eye of the King Krishnadevaraya and other people. He shared his life story with Krishnadevaraya, who granted him the post of the comic poet in the court. Ramakrishna attained fame as a great jester poet. Tenali was instrumental in protecting the King many times, coming to his rescue in critical situations. So Krishnadevaraya praised Tenali very much and this made other ministers jealous of him. One of the minister decided to insult Tenali in front of the king.

The minister then took a bag containing N number of gems numbered from 0 to N-1.He picked some K of the gems and asked the soldiers to distribute it to the people. The minister computed the sum of the numbers on the gems he distributed. He told Tenali only that the sum was divisible by N and asked Tenali to find the number of possible sets of distributed gems.

Help Tenali to find the answer. Since the result may be big return the answer modulo 1,000,000,007.

Input

First line T the number of test cases (1 <= T <= 10)

Followed by T lines containing the value for N, K.

N the number Gems in the bag (1 <= N <= 1000000000).

K the number of Gems distributed (1 <= K <= Min(N, 1000)).

Output

Return the number of possible set of gems distributed modulo 1,000,000,007

Example

Input:
1
7 4

Output:
5

Explanation:

7 gems are numbered 0 to 6 and 4 of them were distributed. Possible sets of gems distributed are {0, 1, 2, 4}, {0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}.