Hãy tính toán các giá trị \(a^b \mod 10^9\) \(+ 7\) một cách hiệu quả.

Lưu ý: Trong bài này, ta giả định rằng \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n:\) số lượng câu hỏi.
• Sau đó là \(n\) dòng, mỗi dòng chứa hai số \(a,b\).

Output

• In ra các giá trị \(a^b \mod 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