Problem1517--pipi染色II

1517: pipi染色II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 120  Solved: 43
[Submit] [Status] [Web Board] [Creator:]

Description

pipi有一颗高度为n满二叉树,根结点的的高度为1
pipi要给每个结点染色,一共有m种不同的颜色,颜色编号为0,1,...,m-1pipi希望给每个结点染成m种颜色的一种,但是有如下要求:
1. 染色为0的结点不能与染色为1的结点有一条边直接相连
2. 染色为1的结点不能与染色为2的结点有一条边直接相连
...
m. 染色为m-1的结点不能与染色为0的结点有一条边直接相连
pipi想知道有多少种合法的染色方案数,由于答案可能很大,只需要输出答案除以10^9+7的余数。

Input

第一行一个整数T(1\le T\le 10000),表示测试用例的组数。
接下来T行每行两个两个整数n,m(1\le n\le 60,3\le m\le 10^9)

Output

输出T行,第i行一个整数表示第i组测试用例的答案。

Sample Input

2
2 3
5 9999

Sample Output

3
708377007

Source/Category

中等