CSES - Exponentiation
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Your task is to efficiently calculate values aba^b modulo 109+710^9+7.

Note that in this task we assume that 00=10^0=1.

Input

The first input line contains an integer nn: the number of calculations.

After this, there are nn lines, each containing two integers aa and bb.

Output

Print each value aba^b modulo 109+710^9+7.

Constraints

  • 1n21051 \le n \le 2 \cdot 10^5
  • 0a,b1090 \le a,b \le 10^9

Example

Input:

3
3 4
2 8
123 123

Output:

81
256
921450052