K次方和

Time Limit: 9000 ms Memory Limit: 262144 KiB

Problem Description

x mod y表示x除以y的余数, 给定整数nk, 计算(mod 1000000007

Input

 

测试数据有T行(1T100),每行两个整数,分别是nk1n10000000001k50)。

Output

 

输出T行,每行一个整数,表示计算的结果。

Sample Input

5 1
4 2
13 5
123456789 1

Sample Output

15
30
1002001
383478132

Hint

 

Source

青岛理工交流赛