Background

$\text{I need you to give me direction.}$

$\text{Even if I have to walk alone through the endless crowd.}$

$\text{To taste wind and frost for you.}$

$\text{I wander far away.}$

$\text{I need you to give me strength.}$

$\text{No matter what, I will be strong.}$

$\text{As long as you give me hope.}$

Source

Problem Description

In a number triangle of size $N$:

• Row $1$ is $1$.
• Row $2$ is $2\sim3$.
• Row $3$ is $4\sim6$.
• Row $4$ is $7\sim10$.
• $\cdots~\cdots$
• Row $N$ contains $N$ numbers, which are $\frac{N(N-1)}{2}+1\sim\frac{N(N+1)}{2}$.

The figure below shows a number triangle with $N=5$.

Let $(i,j)$ denote the $j$-th number in the $i$-th row.

It is known that $(i,j)$ can directly reach $(i+1,j)$ or $(i+1,j+1)$. Conversely, $(i+1,j)$ or $(i+1,j+1)$ can also directly reach $(i,j)$.

Now choose any number as the starting point. When you continuously pass through $K$ distinct numbers, find the maximum possible sum of these $K$ numbers, modulo $10^9+7$.

Input Format

This problem contains multiple test cases.

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

The next $T$ lines each contain two positive integers $N, K$.

Output Format

Output $T$ lines. Each line contains one integer, the answer modulo $10^9+7$.

1
5 5

61

5
2676 1930
5148 3667
5453 4764
16734806 16332913
26943973 33293903 

909411538
587883333
823595806
727601062
965648555

Hint

Sample Explanation

For sample #1, as shown in the figure in the statement, one feasible plan is: start from $13$, $13\rightarrow9\rightarrow14\rightarrow10\rightarrow15$, with sum $13+9+14+10+15=61$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $1\le T\le 10^5$, $1\le\color{red}\dfrac{K+1}{2}\le N\color{black}\le10^9$.

Translated by ChatGPT 5