Background

You are drinking hot cocoa in a snow cave while counting stars. But this time, the stars are replaced by sequences. Clever as you are, you can surely count the sequences clearly.

Problem Description

How many non-decreasing positive integer sequences $a_i$ of length $n$ satisfy:

• $0 < a_1 \le a_2 \le a_3 \dots \le a_n \le k$.
• $\forall i \ne j, a_i + a_j \ne k + 1$.

Output the answer modulo $10^9 + 7$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$.

The next $T$ lines each contain two positive integers $n, k$.

Output Format

Output $T$ lines, each containing one positive integer, the answer.

3
2 2
1145 1419
19198 12321

2
66937457
949924930

Hint

This problem uses bundled testdata.

• $\text{subtask1(20pts)}: T = 5, 1 \le n, k \le 5$.
• $\text{subtask2(80pts)}:$ No special constraints.

For $100\%$ of the testdata, $T \le 100$, $1 \le n, k \le 5 \times 10^6$, and $1 \le \sum n, \sum k \le 6 \times 10^7$.

Translated by ChatGPT 5