Cuộc vui nào cũng đến lúc nào, hành trình nào cũng đến lúc phải kết thúc và cuộc gặp gỡ nào rồi cũng phải nói lời chia tay. Thời gian trôi nhanh như cách mà Ami đánh caro thắng hết cả 20 người trong lớp 12A5 vậy. Mới 6 giờ 9 phút, Ami và LN còn người đạp trước, kẻ ngồi sau, đến bây giờ đã là 10 giờ tối cả rồi. Dù không muốn nhưng Ami cũng đành phải rước LN về thôi. Nhà LN và Ami cũng gần mà – Ami tự an ủi mình.
“Ta lại cách xa giữa muôn vạn trùng khơi
Tuy xa mặt, nhưng trái tim vẫn chẳng rời
Ta cùng hứa, một ngày lại gặp gỡ
Tình cảm vẫn mặn nồng như lúc ta mới quen” Credit Vi Cây Đi
Người ta nói rằng khi anh ở bên em, thời như đọng lại, thế giới như ngừng quay, gió như ngừng thổi, chỉ còn hai ta với những khoảnh khắc ngọt ngào. Nhưng đối với Ami, ở bên cạnh LN, thời gian như dãy Fibonacci vậy. Mới chỉ xuất phát từ 2 số 1 , 1 , mà chỉ khoảng 69 số đã hơn 18 chữ số rồi. À không, Ami nghĩ, số Fibonacci cộng cũng chưa đủ để diễn tả khoảng thời gian mà cậu cho chỉ là khoảnh khắc ấy, phải là dãy số Fibonacci nhân cơ ! Thực ra làm gì có dãy Fibonacci nhân, nhưng Ami thì còn biết trời đất gì nữa, không có thì cậu làm cho nó tồn tại thôi. Ami muốn biết rằng, dãy số Fibonacci nhân ấy tăng nhanh đến mức nào, có bằng 1/696969696969 thời gian ở cạnh người yêu không ?
*Đây là bài cuối cùng nói về mối tình của Ami và LN nhé, từ bài F đến các contest sau, các bạn sẽ được làm quen với lối ra đề của anh CaiWinDao.
Tóm lại, các bạn được cho một dãy số sau :
F1 = a
F2 = b;
FN = FN-1 * FN-2 với n > 2.
Các bạn hãy tính số thứ n của dãy số này chia dư cho một số mod (Fn % mod).
Dữ liệu vào:
4 số nguyên dương a , b , n , mod (a , b <= 109 , n <= 109 , mod <= 103).
Kết quả:
Các bạn cần in ra số Fn % mod.
Ví dụ
Input
1 2 6 6
Output
2
Input
3 4 6 6
Output
0
Giải thích
Ở ví dụ 1, F3 = 2 , F4 = 4 , F5 = 8 , F6 = 32 . 32 mod 6 = 2.
Ở ví dụ 2, F3 = 12 , F4 = 48 , F5 = 576 , F6 = 27648 . 27648 mod 6 = 0.