Hãy để ý memory limit thấp một cách bất thường của bài này (8MB). Happy coding!

Tài và Xỉu đang chơi một trò chơi. Họ có một xâu nhị phân độ dài ~N~, các vị trí được đánh số từ ~1~ đến ~N~, và ~Q~ lượt chơi, được đánh số từ ~0~ đến ~Q-1~. Luật chơi như sau:

• Nếu lượt thứ ~i~ là lượt của Tài, Tài sẽ chọn số ~x_i~ và đảo trạng thái bit ở vị trí ~x_i~ của xâu nhị phân. Chẳng hạn, xâu nhị phân là 00000 và trong lượt của bạn Tài, bạn ấy chọn ~x_i = 3~, thì xâu nhị phân sẽ trở thành 00100.

• Nếu lượt thứ ~i~ là lượt của Xỉu, Xỉu sẽ chọn số ~x_i~ và đưa ra vị trí của bit 1 gần nhất mà có vị trí không nhỏ hơn ~x_i~, nếu không tồn tại thì trả lời là ~0~. Chẳng hạn, xâu nhị phân là 00110, và trong lượt của bạn Xỉu, nếu Xỉu chọn:

  • ~x_i = 1,2,3~, thì đáp án sẽ là ~3~.
  • ~x_i = 4~, đáp án sẽ là ~4~.
  • ~x_i = 5~, đáp án sẽ là ~0~.

Trong trò chơi này, nếu bạn suy nghĩ quá lâu, bạn sẽ thua. Như các bạn có thể thấy, trò chơi này rất bất công, khi mà Xỉu phải tính toán nhiều hơn Tài ở lượt của mình. Vậy nên các bạn hãy giúp Xỉu không thua trò chơi này nhé.

Input

Vì file input có thể khá lớn, nên dữ liệu sẽ được nén lại.

• Trên một dòng, nhập vào ~6~ số nguyên dương ~N~, ~Q~, ~a~, ~b~, ~x~, ~r~ (~1 \leq a, b < n~, ~1 \leq x \leq n~, ~1 < r~).

Cách xử lý: gọi ~i~ là số thứ tự lượt chơi hiện tại, và ~p~ là đáp án của lượt chơi trước đó của Xỉu. Nếu trước đó Xỉu chưa chơi thì ~p = 0~.

• Nếu ~r | i~ thì đó là lượt chơi của Tài, nếu không thì đó là lượt chơi của Xỉu.
• Nếu số thứ tự lượt chơi hiện tại là ~i = 0~, thì ~x_0 = x~. Ngược lại, ta có ~x_i = (a * x_{i-1} + b + p)~ % ~n + 1~, với % là phép chia lấy dư.

Output

Vì file output có thể khá lớn, nên dữ liệu sẽ được nén lại.

• Trình chấm chỉ cần kiểm tra xem chương trình bạn có chạy đúng không, nên bạn chỉ cần in ra tổng kết quả trong các lượt chơi của Xỉu.

Sample Input

4 4 2 1 4 2

Sample Output

6

Giải thích test mẫu:

• Lượt chơi ~0~ là lượt của Tài, ~x_0 = 4~. Xâu nhị phân hiện tại là 0001.
• Lượt chơi ~1~ là lượt của Xỉu, ~x_1 = 2~. Đáp án là ~4~.
• Lượt chơi ~2~ là lượt của Tài, ~x_2 = 2~. Xâu nhị phân hiện tại là 0101.
• Lượt chơi ~3~ là lượt của Xỉu, ~x_3 = 2~. Đáp án là ~2~.

Như vậy kết quả là ~4 + 2 = 6~.

Scoring