P7813 Riddle

$\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](https://www.kugou.com/song-36/1y5t3b.html)

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$.

**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 $T$ lines. Each line contains one integer, the answer modulo $10^9+7$.

#### 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.** | Subtask | Score | $N\le$ | $K\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $30$ | $10^3$ | | | $2$ | $30$ | $10^6$ | | | $3$ | $30$ | $10^9$ | $1$ | | $4$ | $10$ | $10^9$ | | 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