Cho ba số nguyên dương ~A~, ~B~ và ~d~. Xét dãy ~F~ gồm n số nguyên: \(F=(~f_1, f_2, … , f_n~)\) định nghĩa như sau: $$F_i=\begin{cases} A , i = 1 \\ B , i = 2 \\ (F_{i-1}+F_{i-2})\ mod\ d , \forall i>2 \end{cases}$$

Yêu cầu

Hãy cho biết nếu sắp xếp dãy ~F~ theo thứ tự không giảm thì số thứ ~k~ có giá trị là bao nhiêu.

Dữ liệu

Dòng duy nhất chứa 5 số nguyên dương ~n, d, k, A, B~.

Kết quả

Dòng duy nhất xuất ra giá trị tìm được.

Giới hạn

\(n \leq ~10^{18}~, d \leq ~10^5~, k \leq n, A \leq ~10^{18}~, B \leq ~10^{18}~\).

Input

10 10 8 1 1

Output

5