Po muốn chia một đội có ~n+2~ người thành 2 đội để thi đấu với nhau. Đầu tiên Po sẽ chọn người thứ ~n+1~ và ~n+2~ làm đội trưởng hai đội, sau đó mỗi đội trưởng sẽ thay phiên nhau chọn người chơi cho đội của họ. Vì mỗi đội trưởng muốn tạo ra đội mạnh nhất có thể nên họ sẽ chọn người có sức mạnh lớn nhất trong những người còn lại.

Tuy nhiên Po không biết được sức mạnh của những người chơi, Po chỉ biết rằng người đầu tiên có sức mạnh ~s_1=d~, người thứ ~i~ trong ~n-1~ người tiếp theo có sức mạnh được tính bằng công thức:

~s_i = (a * s_{i-1}^2 + b * s_{i-1} + c )~%~1000000~;

Trong đó dấu % là phép chia lấy phần dư;

~ s_{n+1} = s_{n+2} = 1000000 ~

Hãy cho biết hai đội có sự chênh lệch sức mạnh là bao nhiêu?

Dữ liệu vào:

• Một dòng ghi lần lượt các số nguyên ~n,a,b,c,d~ ~(1 ≤ n ≤5.10^6; 0 ≤ a,b,c,d ≤ 100)~

Kết quả:

• Một số nguyên dương cho biết kết quả bài toán

Giới hạn:

• Có 50% số test tương ứng 50% số điểm có ~n≤10^5~
• Có 50% số test còn lại tương ứng 50% số điểm có ~n≤5.10^6~

Ví dụ:

Input

2 1 1 1 1 

Output

2