Hãy tính toán các giá trị \(a^b \bmod 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\)

Constraints

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

Output

• In ra các giá trị \(a^b \bmod 10^9 + 7\)

Example

3
3 4
2 8
123 123

81
256
921450052