Câu lạc bộ Tài chính sinh viên của Đại học Công nghiệp Hà Nội tổ chức trò chơi mô phỏng Nhà đầu tư thông thái. Trong trò chơi có một gói tiết kiệm "lãi kép" rất hấp dẫn: tháng thứ nhất người chơi được thưởng ~a~ xu, và kể từ tháng thứ hai, số xu thưởng của mỗi tháng gấp ~a~ lần số xu thưởng của tháng liền trước. Như vậy tháng thứ ~k~ người chơi được thưởng ~a^k~ xu.

Tổng số xu thưởng sau ~n~ tháng lớn đến mức bảng xếp hạng chỉ hiển thị phần dư của nó khi chia cho một số nguyên dương ~M~.

Yêu cầu

Cho ~T~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~a~, ~n~, ~M~. Với mỗi truy vấn, hãy tính

$$\left(a^1 + a^2 + \cdots + a^n\right) \bmod M .$$

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~T~ – số truy vấn;
• ~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~n~, ~M~ của một truy vấn.

Kết quả ra

Ghi ra ~T~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~ (một số nguyên từ ~0~ đến ~M - 1~).

Ràng buộc

~1 \le T \le 100~; ~1 \le a \le 10^9~; ~1 \le n \le 10^{18}~; ~1 \le M \le 10^9 + 7~.

• Subtask 1 (30% số điểm – test 01–06): tổng các giá trị ~n~ trong một test không quá ~10^6~;
• Subtask 2 (30% số điểm – test 07–12): ~M = 10^9 + 7~ và ~a \ne 1~ trong mọi truy vấn;
• Subtask 3 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Lưu ý: ~M~ không nhất thiết là số nguyên tố; giá trị ~n~ có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

5
2 10 1000
3 4 7
1 20 6
7 3 1
2 1000000000000000000 1000000007

Kết quả ra mẫu 1

46
1
2
0
438952511

Giải thích

Truy vấn 1: ~2 + 4 + 8 + \cdots + 1024 = 2046~, chia ~1000~ dư ~46~. Truy vấn 2: ~3 + 9 + 27 + 81 = 120~, chia ~7~ dư ~1~. Truy vấn 3: ~a = 1~ nên tổng gồm ~20~ số hạng bằng ~1~, và ~20~ chia ~6~ dư ~2~. Truy vấn 4: mọi số nguyên chia cho ~1~ đều dư ~0~. Truy vấn 5: ~n = 10^{18}~, không thể cộng lần lượt từng số hạng.