Benjamin là một cậu học sinh rất giỏi toán và rất hay ham học hỏi. Ở lớp Benjamin luôn là người đặt ra những câu hỏi học búa cho thầy cô và cả bạn bè. Dĩ nhiên là cậu cùng thường xuyên đưa ra những vấn đề và tự mình giải quyết.

Một hôm, sau khi học về cách tính biểu thức ~A^{T}~, cậu liền nghĩ ra một vấn đề đó là có cách nào tính nhanh ~A^{T}~ và lập tức cậu nghĩ ra hướng giải quyết.

Nhưng vẫn không dừng ở đó cậu tự hỏi nếu có ~M~ số ~T_{1}~, ~T_{2}~, ...~T_{M}~ thì có cách nào tính nhanh được biểu thức ~F(T_{1})~ ~+~ ~F(T_{2})~ ~+~ ...~+~ ~F(T_{M})~ hay không và mất nhiều ngày sau đó Benjamin mới nghĩ ra cách làm. Sau khi ra cách làm Benjamin liền lên VNOI đố các VNOI_er giải bài toán trên :D. Biết rằng ~F(x)~ ~= A^{x}.~

Input

• Gồm một dòng chứa ~7~ số ~M~, ~A~, ~a~, ~b~, ~c~, ~d~, ~BASE~.
• ~T_{1} = a~.
• ~T_{i} =~ ~(T_{i-1} \times b + c)~ mod ~d~.

Output

• Gồm một dòng chứa kết quả bài toán mod cho BASE.

Giới hạn

• ~M \le 2 \times 10^{7}~.
• ~A~, ~d \le 10^{12}~.
• ~BASE \le 10^{9}~.
• ~a~, ~b~, ~c \le 10^{5}~.
• ~40\%~ số test, ~M \le 10^{5}~.
• ~M~, ~A~, ~a~, ~b~, ~c~, ~d > = 1~.

Sample Input

1 8 1 1 1 1 2

Sample Output

0