Its Leo's birthday today and he has got packets of chocolates. Now he is thinking to distribute the chocolates to his friends in his class. But he want to distribute the chocolates in a unique way. He can give any number of chocolates to any number of his friends provided that all chocolates are distributed. Let say he has got 'N' chocolates and there are 'P' number of friends in his class. So he can give either zero, one or many chocolates to one or two or many friends (among P friends). Now you have to help him with calculating number of ways so that he could complete his work.
The answer could be huge so please output your answer with modulo (10^9 + 7).

Input

• First line contains T, the number of test cases.
• First line of each test case contains two space-separated integers N and P representing the number of chocolates and number of friends respectively.

Output

• Output your answer modulo(10^9+7).

Constraints

• 1<= T<= 10^5
• 1<= N<= 5*10^6
• 1<= P<= 5*10^6

Subtasks

Subtask #1: (20 points)

• 1&lt= T&lt= 10^5
• 1&lt= N, P&lt= 5*10^4

• Original Constraints

Example

Input:
1
2 2

Output:
3

Explanation

Leo has 3 ways to distribute all 2 chocolates as he can give either 2 chocolates to his first friend or he can give 2 chocolates to his second friend or he can give 1-1 chocolate to both of his friends.

Problem Author: Shubham Kabra