UOJ Logo

NOI.AC

#66. 求和

统计

求和

给一个 $n$ 行 $t$ 列的矩阵,矩阵第 $i$ 行第 $j$ 列的元素是 $i+j$。

定义矩阵第 $i$ 行的积为第 $i$ 行所有元素的乘积。

现在要你求矩阵所有行的积的和。答案可能很大,所以 mod $1000000007 (10^9+7)$ 输出。

输入格式

第一行一个整数 $T$ 表示数据组数。

后面 $T$ 行每行两个数 $n$ 和 $t$。

输出格式

一共 $T$ 行每行一个数表示答案。答案模 $10^9+7$。

样例1

输入

2
3 1
2 2

输出

9
18

样例2

样例数据

数据范围

10%, $T\le 100$, $n\le 1000$

另20%, $T\le 10$, $n\le 1e7$

另20%, $T\le 10000$, $n\le 1e7$

另20%, $T\le 10000$, $n\le 1e8$

100%, $1\le T\le 10000$, $1\le n\le 1e10$, $1\le t\le 1000$