Background

Although this is a C, it still is.

Problem Description

Given positive integers $n, k$, find how many positive integer sequences $a$ of length $n$ satisfy:

• $0 < a_1 \le a_2 \le a_3 \le \cdots \le a_n \le k$;
• $\forall\ i \not= j$, $a_i + a_j \le k + 1$.

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

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, the input contains one line with two positive integers $n, k$.

Output Format

For each test case, output one line with one integer, representing the answer.

5
2 2
1 3
4 5
4030 218
1145 1419

2
3
20
571656908
172735629

Hint

[Sample Explanation]

For the $1$st test case, all sequences that satisfy the requirements are $(1, 1)$ and $(1, 2)$.

For the $2$nd test case, all sequences that satisfy the requirements are $(1)$, $(2)$, and $(3)$.

[Constraints]

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 2 \times 10^5$, $1 \le n, k \le 10^7$.

This problem uses bundled test cases.

Translated by ChatGPT 5