Một số kẻ chơi khăm đã xem quá nhiều kênh Discovery Channel và giờ họ muốn tạo ra một "tam giác mùa màng" trong đêm. Họ muốn xây dựng nó bên trong một cánh đồng lớn trông giống như một lưới các ô vuông đều nhau khi nhìn từ trên cao. Có một số cây được trồng trên cánh đồng. Mỗi cây nằm ở giao điểm của hai đường lưới (một điểm lưới).

Những kẻ chơi khăm muốn các đỉnh của tam giác mùa màng phải nằm tại các vị trí có cây này. Ngoài ra, để tam giác thêm phần thú vị, họ muốn trọng tâm của tam giác đó cũng phải nằm tại một điểm lưới. Chúng tôi nhắc lại rằng nếu một tam giác có các đỉnh là \((x_1, y_1)\), \((x_2, y_2)\) và \((x_3, y_3)\), thì trọng tâm của tam giác này sẽ có tọa độ là \(((x_1 + x_2 + x_3) / 3, (y_1 + y_2 + y_3) / 3)\).

Bạn được cho một tập hợp các điểm với tọa độ nguyên là vị trí của tất cả các cây trên lưới. Bạn được yêu cầu tính xem có bao nhiêu tam giác có thể tạo thành từ 3 đỉnh phân biệt trong tập hợp các điểm này sao cho trọng tâm của chúng cũng là một điểm lưới (tức là trọng tâm có tọa độ nguyên).

Nếu một tam giác có diện tích bằng 0, chúng ta vẫn coi đó là một tam giác hợp lệ.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test theo sau. Mỗi bộ test bao gồm một dòng chứa các số nguyên \(n, A, B, C, D, x_0, y_0\) và \(M\) cách nhau bởi đúng một dấu cách. \(n\) là số lượng cây trong tập dữ liệu đầu vào.

Sử dụng các số \(n, A, B, C, D, x_0, y_0\) và \(M\), đoạn mã giả sau đây sẽ in ra tọa độ của các cây trong tập dữ liệu. \(mod\) biểu thị phép toán lấy số dư.

Các tham số sẽ được chọn sao cho tập hợp các cây đầu vào không có điểm nào trùng nhau.

X = x0, Y = y0
print X, Y
for i = 1 to n-1
  X = (A * X + B) mod M
  Y = (C * Y + D) mod M
  print X, Y

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(X\): " trong đó \(X\) là số thứ tự bộ test (bắt đầu từ 1). Tiếp theo là một số nguyên cho biết số lượng tam giác có thể được đặt tại 3 cây phân biệt và có trọng tâm là một điểm lưới.

Ràng buộc

• \(1 \le N \le 10\).
• \(0 \le A, B, C, D, x_0, y_0 \le 10^9\).
• \(1 \le M \le 10^9\).

Phân nhóm

• Tập kiểm tra 1 (Small - Visible): \(3 \le n \le 100\).
• Tập kiểm tra 2 (Large - Hidden): \(3 \le n \le 100000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
4 10 7 1 2 0 1 20
6 2 0 2 1 1 2 11

Case #1: 1
Case #2: 2

Nguồn

Google Code Jam 2008, Vòng 1B, bài Crop Triangles.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.