Lũy thừa siêu nhanh

Cho các bộ ba số nguyên không âm \((a, b, c)\), hãy tính giá trị \(a^{b^c} \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a, b, c\) (\(0 \le a, b, c \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^{b^c} \pmod{10^9 + 7}\) tương ứng với mỗi bộ ba \((a, b, c)\) trong dữ liệu vào.

Example

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(n, b, c \leq 4\).
• Subtask \(2\) (\(30\%\) số điểm) : \(c = 1\).
• Subtask \(3\) (\(40\%\) số điểm) : không có ràng buộc gì thêm.