背景

lh大神正在参加物理考试,但是这次的期中考试卷又是姥姥出的,全都是1维的碰撞、2维的平抛、3维的电磁感应,显然水的一B。lh大神多出了很多很多无聊的时间,于是他开始思考起来与XJS大神讨论过的超弦理论,当然lh大神只思考了一会,就睡着了。

描述

梦中他来到了一个m维世界。这个世界有一个王,The king of the dimension。他管理者这个世界所有的生物。麻烦的是这个世界的生物实在是太多了(想一下三维世界的人就懂了),王经常为此晕头转向。于是他把所有的生物按种类分成了N种。对于第i维世界,第j种生物可以生存的个数为第i-1维世界同种生物的j倍(高维世界物质多,竞争压力小⊙﹏⊙b汗),第0维任何一种生物都只能生存一个。现在王决定向到来的lh大神进行提问,前n种生物在第m维世界中共有多少个。王不喜欢看大的数,所以回答对1000000007取模(显然输出的数应该是非负数)。

输入格式

输入含多组数据,第一行一个正整数Q,表示这个测试点内的数据组数。

接下来Q组数据,每组数据一行,两个整数N,M。

输出格式

共Q行,每行一个询问取模过的答案。

样例输入1:

3

1 1

2 2

3 3

样例输入2:

2

4 2

4 3

 

样例输出1:

1

5

36

样例输出2:

30

100

 

数据范围与约定

 

20% 1<=Q<=100 1<=N<=10^5 1<=M<=10
40% 1<=Q<=100 1<=N<=10^5 1<=M<=500
另有20% Q=1 1<=N<=10^7 1<=M<=500
100% 1<=Q<=100 1<=N<=10^9 1<=M<=500
 

样例解释

各位神犇应该不需要解释吧STQ
 

来源

 经典数学题