Lũy Thừa Hai Tầng · canuc80k0835 · Thuật toán Canuc80k

Cho $q$ bộ ba số nguyên không âm $(a, b, c)$ . Với mỗi bộ, hãy tính

a^{b^{c}} mod 1, 000, 000, 007.

Trong bài này, mọi biểu thức $0^{0}$ đều được quy ước bằng $1$ . Quy ước này áp dụng cả khi tính $b^{c}$ lẫn lũy thừa bên ngoài.

Input

Dòng đầu chứa số nguyên $q$ .
Mỗi trong $q$ dòng tiếp theo chứa ba số nguyên $a, b, c$ .

Output

Với mỗi bộ dữ liệu, in kết quả trên một dòng.

Constraints

$1 \leq q \leq 1 0^{5}$ .
$0 \leq a, b, c \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $q \leq 100$ và $a, b, c \leq 1000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Bộ đầu cho $2^{3^{2}} = 2^{9} = 512$ . Ở bộ thứ hai, $0^{7} = 0$ nên lũy thừa ngoài có số mũ $0$ ; ở bộ thứ ba, $0^{0} = 1$ ở tầng trong nên kết quả là $0^{1} = 0$ . Hai bộ còn lại lần lượt là $0^{8} = 0$ và $7^{1} = 7$ .

Phân tích: Đặt P=1,000,000,007. Khi số mũ E=b^c dương và a không chia hết cho P, định lý Fermat nhỏ cho phép thay E bằng E mod (P-1). Giá trị này được tính bằng lũy thừa nhị phân modulo P-1.
Phân tích: Cần tách các trường hợp không nguyên tố cùng nhau với P. Do 0≤a≤10^9<P, chỉ có a=0 cần chú ý. Số mũ b^c bằng 0 đúng khi b=0,c>0; khi đó kết quả là a^0=1. Trong mọi trường hợp còn lại, số mũ dương; nếu a=0 thì kết quả bằng 0.
Thuật toán: Với mỗi bộ (a,b,c):
Thuật toán: 1. Nếu b=0,c>0, in 1. 2. Nếu a=0, in 0. 3. Tính e=b^c mod (P-1) bằng binary exponentiation. 4. In a^e mod P.
Chứng minh đúng: Nhánh đầu nhận đúng và chỉ đúng trường hợp số mũ ngoài bằng 0, nên quy ước a^0=1 được áp dụng chính xác. Sau khi bỏ nhánh đó, số mũ dương; nhánh a=0 cho đúng 0. Ở nhánh còn lại, gcd(a,P)=1; Fermat bảo đảm giảm số mũ modulo P-1 không đổi phần dư. Hai lần lũy thừa nhị phân tính đúng các phần dư cần thiết, nên thuật toán đúng cho mọi bộ.
Độ phức tạp: Mỗi bộ cần O(log c + log P) thời gian và O(1) bộ nhớ phụ.