Cho ~1~ bảng kích thước ~N \times N~ được chia thành các ô vuông đơn vị. Mỗi ô vuông có thể có màu đen hoặc trắng. Bây giờ, định nghĩa ~1~ hình chữ nhật tốt là ~1~ hình chữ nhật có các cạnh song song với cạnh của bảng và chỉ chứa các ô vuông màu trắng. ~1~ hình chữ nhật được gọi là hoàn hảo, nếu nó là ~1~ hình chữ nhật tốt, và không tồn tại ~1~ hình chữ nhật tốt nào khác chứa nó (tức không thể mở rộng hình chữ nhật này sang trái, phải, trên hay dưới).

Yêu cầu: Xác định số hình chữ nhật hoàn hảo của bảng đã cho.

Lưu ý:

Để giảm kích thước của input, bảng sẽ được tô màu theo quy tắc sau:

• Ban đầu bảng chỉ chứa các ô vuông màu trắng

• Sinh ~2~ dãy số ~X~ và ~Y~ độ dài ~m~ theo quy tắc

  • ~X_0 = x_0 \bmod N, Y_0 = y_0 \bmod N~
  • ~X_i = (X_{i - 1} \times a + b) \bmod N~, ~Y_i = (Y_{i - 1} \times c + d) \bmod N~ với ~1 \le i < m~,
  • trong đó ~x_0, y_0, a, b, c, d, m~ là các số được cho trước, và ~P \bmod Q~ kí hiệu là phần dư của phép chia ~P~ cho ~Q~

• Tô đen các ô có tọa độ ~(X_0, Y_0), (X_1, Y_1), \dots, (X_{m - 1}, Y_{m - 1})~. (Tọa độ của bảng được đánh số từ ~0~ đến ~N - 1~ theo thứ tự từ trái qua phải, và từ trên xuống dưới)

Input

• ~1~ dòng duy nhất gồm ~8~ số nguyên ~N~, ~m~, ~x_0~, ~a~, ~b~, ~y_0~, ~c~, ~d~ như mô tả trong đề bài

Output

• ~1~ dòng duy nhất ghi ra số lượng hình chữ nhật hoàn hảo thu được

Giới hạn

• ~0 < N \le 2000~
• ~1 \le m \le 4000000~
• ~0 \le a~, ~b~, ~c~, ~d~, ~x_0~, ~y_0~ ~\le 2000~

Sample Input 1

5 1 2 0 0 2 0 0

Sample Output 1

4

Sample Input 2

4 4 0 1 1 0 1 1

Sample Output 2

6

Sample Input 3

10 20 4 76 2 6 2 43

Sample Output 3

12