Dãy số \(a_1, a_2, \dots, a_n\) được lập theo quy tắc sau:

• \(a_1 = x, a_2 = y\)
• \(a_k = (a_{k-1} + a_{k-2}) \pmod M\) với mọi \(k = 3, 4, \dots, n\)

Ở đây phép toán \(p \pmod q\) là phép lấy phần dư khi chia \(p\) cho \(q\) (phép % trong ngôn ngữ C++ và Python).

Cho số nguyên dương \(S\). Hãy tìm dãy con \(a_i, a_{i+1}, \dots, a_j\) có số lượng phần tử nhỏ nhất sao cho: \(a_i + a_{i+1} + \dots + a_j \geq S\).

Input

• Một dòng duy nhất chứa 5 số nguyên \(n, x, y, M, S\) (\(2 \leq n \leq 2 \cdot 10^5\); \(1 < M \leq 10^4\); \(0 \leq x, y < M\); \(1 \leq S \leq 10^{15}\)) cách nhau bằng khoảng trống.

Output

• Một số nguyên duy nhất là số lượng phần tử của dãy con tìm được. Nếu không tồn tại dãy con thoả mãn thì in \(-1\).

Example

10 1 1 7 19

5

Constraints

• Có \(40\%\) số tests ứng với \(40\%\) số điểm của bài có \(n \leq 300\);
• \(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có \(n \leq 5000\);
• \(30\%\) số tests còn lại không có ràng buộc bổ sung.