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\)

Constraints

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

Output

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

Example

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764