FBRICK - Xếp hình

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

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 , ... 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 (i > 2) bằng 2 × A 2 × A i  – 1 – A­ 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 ≤ 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 ≤ A 2 , M ≤ 10 9 , 2≤ N ≤ 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.

Example

Input:

2

1 10 1000

2 3 100

Output:

10

54

  • Người up: voj
  • Nguồn bài: CEPC 2008