Viết chương trình tính \(a^{b^c}\) modulo \(10^9+7\). Giả sử \(0^0=1\).

Input

• Dòng đầu tiên là số lượng bộ test \(t\)
• \(t\) dòng tiếp theo, mỗi dòng chứa \(3\) số \(a,b,c\)

Output

• \(a^{b^c}\) modulo \(10^9+7\)

Điều kiện

• \(1 \le n \le 10^5\)
• \(0 \le a,b,c \le 10^9\)

Sample Input 1

3
3 7 1
15 2 2
3 4 5

Sample Output 1

2187
50625
763327764