Bạn cần tính hiệu quả giá trị: ~a^{b^c}~ mod ~10^9+7~.

Lưu ý: Giá trị của ~0^0~ = 1

Đầu vào:

Dòng đầu tiên chứa số nguyên ~n~: số lượng phép tính.

~n~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a, b, c~.

Đầu ra:

In ra ~n~ dòng, mỗi dòng là kết quả của phép tính tương ứng.

Ví dụ :

Input:

3
3 7 1
15 2 2
3 4 5

Output:

2187
50625
763327764