题目背景

$\text{我需要你给我方向}$

$\text{哪怕要我独自穿过人海茫茫}$

$\text{为了你尝风霜}$

$\text{我流浪远方}$

$\text{需要你给我力量}$

$\text{无论如何我会坚强}$

$\text{只要你给我希望}$

Source

题目描述

在一个大小为 $N$ 的数字三角形中：

• 第 $1$ 行为 $1$；
• 第 $2$ 行为 $2\sim3$；
• 第 $3$ 行为 $4\sim6$；
• 第 $4$ 行为 $7\sim10$；
• $\cdots~\cdots$
• 第 $N$ 行包含 $N$ 个数字，为 $\frac{N(N-1)}{2}+1\sim\frac{N(N+1)}{2}$。

下图展示了一个 $N=5$ 的数字三角形。

---

记 $(i,j)$ 表示第 $i$ 行第 $j$ 个数字。

已知 $(i,j)$ 能直接到达 $(i+1,j)$ 或 $(i+1,j+1)$，反之，$(i+1,j)$ 或 $(i+1,j+1)$ 也能直接到达 $(i,j)$。

现在任选一个数字作为起点，求 连续 地经过 $K$ 个 不同 的数字时，这 $K$ 个数的和的最大值，对 $10^9+7$ 取模。

输入格式

本题包含多组数据测试。

第一行，输入一个正整数 $T$，表示询问组数。

接下来 $T$ 行，每行输入两个正整数 $N,K$。

输出格式

共 $T$ 行，每行输出一个整数，表示答案对 $10^9+7$ 取模的结果。

1
5 5

61

5
2676 1930
5148 3667
5453 4764
16734806 16332913
26943973 33293903 

909411538
587883333
823595806
727601062
965648555

提示

样例说明

对于样例 #1，如题面中的图所示，一种可行的方案是：以 $13$ 为起点，$13\rightarrow9\rightarrow14\rightarrow10\rightarrow15$，和为 $13+9+14+10+15=61$。

数据范围

本题采用捆绑测试。

Subtask	分值	$N\le$	$K\le$
$1$	$30$	$10^3$
$2$		$10^6$
$3$		$10^9$	$1$
$4$	$10$

对于 $100\%$ 的数据：$1\le T\le 10^5$，$1\le\color{red}\dfrac{K+1}{2}\le N\color{black}\le10^9$。