Dãy \(Fibonacci\) là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử \(0\) và \(1\), các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Dãy số \(Fibonacci\) rất đặc biệt này được Leonardo \(Fibonacci\) (hay còn có tên tên khác là Leonarda da Pisa) là một nhà toán học người Ý công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đố qua \(2\) bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực. Henry E Dudeney (1857 - 1930) (là một nhà văn và nhà toán học người Anh) nghiên cứu ở bò sữa, cũng đạt kết quả tương tự. Thế kỉ XIX, nhà toán học Edouard Lucas (người Pháp) xuất bản một bộ sách bốn tập với chủ đề toán học giải trí, ông đã dùng tên \(Fibonacci\) để gọi dãy số kết quả của bài toán từ cuốn Liber Abaci – bài toán đã sinh ra dãy \(Fibonacci\). Dãy số này hầu như biến hóa vô tận. Chính đều đó làm cho bao nhà toán học (chuyên nghiệp lẫn nghiệp dư) và ngay cả chúng ta say mê nghiên cứu, khám phá về nó.

Xét dãy số fib3 là một biến thể của dãy số \(Fibonacci\), với ba số nguyên không âm \(a, b, c\) ta xây dựng dãy số theo quy tắc sau:

\(fib3(n) = \begin{cases} n & \text{if } n \le 3\\ a.fib3(n-1) + b.fib3(n-2) + c.fib3(n-3) & \text{if n % 3=1}\\ b.fib3(n-1) + c.fib3(n-2) + a.fib3(n-3) & \text{if n % 3=2}\\ c.fib3(n-1) + a.fib3(n-2) + b.fib3(n-3) & \text{if n % 3=0} \end{cases} \)

Yêu cầu

• Cho \(5\) số nguyên không âm \(a, b, c, k, n\). Hãy tính số \(fib3(n)\)%\(k\).

Dữ liệu vào

• Một dòng chứa \(5\) số nguyên không âm \((a, b, c, k, n)\) \((a, b, c, k \le 10^9)\)

Dữ liệu ra

• Chứa một số là kết quả tìm được tương ứng với dữ liệu vào

Input 1

1 1 1 100 4

Output 1

6

Input 2

1 2 3 997 4

Output 2

10

Input 3

127415 652138 397756 563213 704020

Output 3

43525

Ràng buộc

• Subtask \(1\): \(n \le 10^6\)
• Subtask \(2\): \(n \le 10^9, a=b=c=1\)
• Subtask \(3\): \(n \le 10^9\)