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
Comments