Your task is to efficiently calculate values \(a^b\) modulo \(10^9+7\).

Note that in this task we assume that \(0^0=1\).

Input

• The first input line contains an integer \(n\): the number of calculations.
• After this, there are \(n\) lines, each containing two integers \(a\) and \(b\).

Output

• Print each value \(a^b\) modulo \(10^9+7\).

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(0 \leq a, b \leq 10^9\)

Example

Sample input

3
3 4
2 8
123 123

Sample output

81
256
921450052