Sau khi học được phép lũy thừa nhị phân, Per được thầy giáo cho bài toán sau:

Cho ba số nguyên không âm ~a~, ~b~, ~c~, hãy tính nhanh giá trị ~a^{b^c}~ chia dư cho ~10^9 + 7~.

Lưu ý rằng ~a^0 = 1~ với mọi ~a~ (kể cả ~a = 0~).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~q~ — số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~b~, ~c~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là giá trị ~a^{b^c}~ chia dư cho ~10^9 + 7~ của truy vấn thứ ~i~.

Ví dụ

Đầu vào:

1
2 3 1

Đầu ra:

8

Giải thích: ~b^c = 3^1 = 3~, nên đáp án là ~2^3 = 8~.

Giới hạn

• ~1 \le q \le 10^5~
• ~0 \le a, b, c \le 10^9~