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) = \left\{ \begin{array}{cl} n & if\ n \le 3 \\ a.fib3(n-1)+b.fib3(n-2)+c.fib3(n-3) & if\ n\%3=1\\ b.fib3(n-1)+c.fib3(n-2)+a.fib3(n-3) & if\ n\%3=2\\ c.fib3(n-1)+a.fib3(n-2)+b.fib3(n-3) & if\ n\%3=3\\ \end{array} \right.\)
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\).

Input

• Nhiều dòng, mỗi dòng chứa 5 số nguyên không âm (\(a, b, c, k, n\)) (\(a, b, c, k≤10^9\)).

Output

• Mỗi dòng tương ứng của dữ liệu vào, in ra một số là kết quả tìm được tương ứng với dữ liệu vào.

Scoring

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

Example

1 1 1 100 4    

6

1 1 1 111539786 1    

1

Nguồn: CĐ DHBB