Coronaviruses reproduce in groups. Recently, they have decided to reproduce themselves on a large scale and they call this project – “Coroproduction”.

There are N coronaviruses in a group with each coronavirus having strength S. While reproducing, the i^th coronavirus can transfer P_i strength to the offspring, where P_i is any integer between 1 and S.

The strength of the offspring is equal to the product of all the strengths it received from its parents, that is, the product of all P_i (1 < i < N). It is desired that the strength of the offspring is an even number.

Can you find the no. of ways in which the N coronaviruses can reproduce an offspring whose strength is an even number? Since the answer can be large, compute it modulo 10⁹ + 7.
 

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and the only line of each test case contains two space-separated integers – N, S.
   

Output:

For each test case, print a single line containing one integer - the required no. of ways modulo 10⁹ + 7.
 

Constraints:

• 1 < T < 10⁴
• 1 < N < 10¹⁸
• 2 < S < 10⁹
   

Test Files:

Test File #1 (10 points):

• 1 < N < 20
• S = 2

Test File #2 (10 points):

• 1 < N < 8
• 2 < S < 10

Test File #3 (30 points):

• 1 < N < 100

Test File #4 (50 points): original constraints