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