Xếp hình

View as PDF

Submit solution


Points: 0.39 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
CEPC 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nguyên rất thích trò chơi xếp tháp. Tòa tháp của Nguyên bao gồm những khối lăng trụ đứng có đáy hình vuông và chiều cao bằng ~1~. Nguyên 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 học toán, Nguyên được cô giáo dạy về cách tính thể tích các hình khối đơn giản. Nguyên thích thú với kiến thức mới học được và cậu ta muốn tính thể tích tòa tháp của mình.

Tháp của Nguyên 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, \dots A_N~. Dãy ~A~ được tạo như sau:

  1. ~A_{1} = 1~.
  2. ~A_{2}~ sẽ là một số dương tùy ý mà Nguyên chọn trong mỗi lần chơi để tránh nhàm chán.
  3. ~A_{i} =2 \times A_{2} \times A_{i - 1} - A­_{i - 2}~ với ~i>2~

Nguyên biết rõ thể tích hình một 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, Nguyên muốn nhờ bạn viết một chương trình giúp cậu 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 \leq 10~ là số bộ dữ liệu.
  • ~K~ dòng tiếp: Mỗi dòng ghi ~3~ số nguyên ~A_{2}~, ~N~, ~M~ tương ứng với một bộ dữ liệu. ~(1 \leq A_{2}~, ~M \leq 10^{9}~, ~2 \leq N \leq 10^{9})~

Output

  • Với mỗi bộ test ghi ra một số duy nhất là kết quả tương ứng trên một dòng.

Sample Input

2
1 10 1000
2 3 100

Sample Output

10
54

Comments

Please read the guidelines before commenting.


There are no comments at the moment.