Nhiệm vụ của bạn là tính toán các giá trị ~a^{b^c}~ modulo ~10^9 + 7~.

Lưu ý: Giả định rằng ~0^0 = 1~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm ba số nguyên không âm ~a~, ~b~ và ~c~ ~(0 \leq a,b,c \leq 10^9)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a^{b^c}~ modulo ~10^9 + 7~.

Sample Input

3
3 7 1
15 2 2
3 4 5

Sample Output

2187
50625
763327764