Có $T$ truy vấn, mỗi truy vấn nhập vào ba số nguyên không âm $a,\ b,\ c$. Tính giá trị biểu thức $a^{b^c}$ modulo $10^9+7$.

Input

• Dòng đầu tiên chứa số nguyên dương $T$ là số lượng truy vấn.
• $T$ dòng tiếp theo, mỗi dòng gồm ba số nguyên không âm $a,\ b$ và $c$.

Output

• Gồm $T$ dòng trả lời cho $T$ truy vấn, mỗi dòng in ra giá trị của $a^{b^c}$ modulo $10^9+7$

Ràng buộc

• $1\leq n\leq10^5$;
• $0\leq a,\ b,\ c\leq10^9$.

Ví dụ

Sample input

3
2 5 7
4 9 3
6 8 15

Sample output

327900077
941122123
666373461