Nhiệm vụ của bạn là tính toán các giá trị một cách hiệu quả a^b môđun 10^9+7. Lưu ý rằng trong nhiệm vụ này chúng tôi giả định rằng a^0=1.

Đầu vào

Dòng đầu tiên chứa một số nguyênN: số lượng phép tính. Sau đó, có N các dòng, mỗi dòng chứa hai số nguyên a Và b.

Đầu ra

In từng giá trị a^b môđun 10^9+7.

Ví dụ

Đầu vào:

3
3 4
2 8
123 123

Đầu ra:

81
256
921450052