Việc của bạn là tính toán hiệu quả giá trị \(a^{b^c}\) modulo \(10^9 + 7\).

Lưu ý rằng trong bài này, ta cho rằng \(0^0 = 1\).

Input

• Dòng đầu tiên là một số nguyên \(n\): số lượng phép tính.
• Tiếp theo là \(n\) dòng, mỗi dòng chứa ba số nguyên \(a, b\) và \(c\).

Output

• In ra từng giá trị \(a^{b^c}\) modulo \(10^9+7\).

Constraints

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

Example

Sample input

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764