Dãy số ~a_1, a_2, \dots, a_n~ được lập theo qui tắc sau: ~a_1 = x, a_2 = y, a_k = (a_{k-1} + a_{k-2}) \bmod M~ với mọi ~k = 3, 4, \dots, n~ Ở đây phép toán ~p \bmod 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~.

Yêu cầu: 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 \ge S~.

Input

Một dòng duy nhất chứa ~5~ số nguyên ~n, x, y, M, S~ ~(2 \le n \le 2 \times 10^5, 1 < M \le 10^4, 0 \le x, y < M, 1 \le S \le 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~.

Scoring

Sample Input 1

10 1 1 7 19

Sample Output 1

5

Notes

Dãy số được tạo ra là ~1, 1, 2, 3, 5, 1, 6, 0, 6, 6~.

Dãy con ngắn nhất có tổng lớn hơn hoặc bằng ~19~ là ~1, 6, 0, 6, 6~.