题目背景

这个一个难度更高的数学问题。

题目描述

请同学们计算一下公式：

$$\sum_{i = 1}^{n}{i^k} \ mod \ 1000000007$$

输入格式

输入多行。

第一行输入一个 $t$ ，代表有 $t$ 组测试。

接下来 $t$ 行，每行输入两个正整数 $n, k$ 。

输出格式

输出 $t$ 行。

每行输出 $\sum_{i = 1}^{n}{i^k} \ mod \ 1000000007$ 的结果。

样例 #1

样例输入 #1

1
3 3

样例输出 #1

36

样例 #2

样例输入 #2

1
10 10

样例输出 #2

914341827

样例 #3

样例输入 #3

1
100 100

样例输出 #3

568830579

样例 #4

样例输入 #4

5
1 1
2 1
5 1
1000 1
100 1

样例输出 #4

1
3
15
500500
5050

提示

样例解释】：

【样例解释1】：$\sum_{i = 1}^{3}{i^3} \ mod \ 1000000007 = (1^3 + 2^3 + 3^3) \ mod \ 1000000007 = (1 + 8 + 27) \ mod \ 1000000007 = 36$ 。

数据范围】：

对于 $10\%$ 的数据 $1 \leq t \leq 10^2, 1 \leq n \leq 10^3, k = 1$ 。

对于 $20\%$ 的数据 $1 \leq t \leq 10^2, 1 \leq n \leq 10^3, k = 2$ 。

对于 $40\%$ 的数据 $1 \leq t \leq 10^2, 1 \leq n, k \leq 10^2$ 。

对于 $100\%$ 的数据 $1 \leq t \leq 10^3, 1 \leq n, k \leq 10^{3}$ 。