Shopping Spree Problem Statement

Preeti plans to shop for her father's birthday at a store with unlimited quantities of N different items. She has a budget that allows her to buy a maximum of K items. Help Preeti determine the number of different ways she can purchase these items, where two ways are considered distinct if at least one item quantity differs.

Input:

The first line of the input contains an integer T, representing the number of test cases.
Each test case consists of a single line with two integers, N and K, indicating the number of item types and the maximum number of items Preeti can buy, respectively.

Output:

For each test case, output a single line with the number of different ways to purchase the items.

Example:

Input:
2
2 2
3 3
Output:
3
10

Constraints:

• 1 <= T <= 10
• 1 <= N <= 1000
• 1 <= K <= 1000

As the answer can be large, return your result modulo 10⁹ + 7.

Note:

Implement the function; do not print anything as it is handled internally.