Farmer John rất yêu những cô bò của mình nên đã quyết định chơi trò xây tòa tháp đẹp trong trang trại của mình để các cô bò vừa gặm cỏ vừa ngắm và chụp ảnh với tòa tháp, điều này giúp chất lượng sữa bò tốt hơn.

Tòa tháp của FJ bao gồm những khối lăng trụ đứng có đáy là hình vuông và chiều cao bằng 1. FJ sẽ xếp các khối lăng trụ chồng lên nhau để tạo thành một tòa tháp cao.

Mới đây trong lớp tập huấn, FJ được giáo sư dạy về cách tính thể tích các hình khối đơn giản. FJ thích thú với kiến thức mới học được và ông ta muốn tính thể tích tòa tháp của mình.

Tháp của FJ bao gồm ~N~ khối lăng trụ đứng chiều cao 1 và có đáy hình vuông và độ dài cạnh đáy từ trên xuống dưới theo thứ tự là ~A_1, A_2, ..., A_N~. Dãy ~A~ được tạo như sau:

• ~A_1 = 1~.
• ~A_2~ là một số dương tùy ý mà FJ sẽ chọn trong mỗi lần chơi để tránh nhàm chán.
• ~A_i (i > 2) = 2 \times A_2 \times A_{i-1} - A_{i-2}~.

FJ biết rõ thể tích hình lăng trụ sẽ bằng chiều cao nhân với diện tích đáy nhưng vì ngại tính toán, FJ muốn nhờ bạn viết một chương trình giúp ông ta.

Kết quả có thể rất lớn vì vậy bạn chỉ cần ghi ra theo modulo ~M~ với ~M~ là một số nguyên dương cho trước.

Input

• Dòng 1: Ghi số nguyên dương ~K~ là số bộ dữ liệu.
• ~K~ dòng tiếp theo: Mỗi dòng ghi 3 số nguyên ~A_2, N, M~ tương ứng với một bộ dữ liệu.

Output

• Với mỗi bộ dữ liệu ghi ra một số duy nhất là thể tích tòa tháp tương ứng trên một dòng.

Sample Input 1

2
1 10 1000
2 3 100

Sample Output 1

10
54

Subtasks

• ~1 \le A_2, M \le 10^9+7; K \le 200~; | Subtask | Điểm | Ràng buộc | |---|---|---| | 1 | ~3.5~ | ~N \le 2 \times 10^5~. | | 2 | ~3.5~ | ~N \le 10^9~. |