Tuples and Tuples

[HarshDutt17]

Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A1,A2,…,AN) such that 0≤A1,A2,…,AN≤2M−1 and A1&A2&…&AN=0, where & denotes the bitwise AND operator.

Since the number of tuples can be large, output it modulo 10**9+7

Input
The first line contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains two integers N and M.

Output:
For each test case, output in a single line the answer to the problem modulo 10**9+7

Sample Input:
4
1 2
2 2
4 2
8 4

Sample Output:
1
9
225
228250597