Bạn đang lái xe trên đường cao tốc thì bị cảnh sát giao thông bắt vì chạy quá tốc độ. Hóa ra họ đã theo dõi bạn, và họ ngạc nhiên trước thực tế là bạn đã tăng tốc suốt thời gian qua mà không hề sử dụng phanh! Và bây giờ bạn tuyệt vọng tìm một lý do để giải thích điều đó.

Bạn quyết định rằng sẽ hợp lý nếu nói "tất cả các biển báo giới hạn tốc độ mà tôi nhìn thấy đều theo thứ tự tăng dần, đó là lý do tại sao tôi liên tục tăng tốc". Viên cảnh sát cười đáp lại, và cho bạn biết tất cả các biển báo được đặt dọc theo đoạn đường cao tốc bạn đã đi, và nói rằng khó có khả năng bạn may mắn đến mức chỉ nhìn thấy một phần của những biển báo này theo thứ tự tăng dần.

Bây giờ bạn cần ước tính khả năng đó, hay nói cách khác, tìm xem có bao nhiêu dãy con khác nhau của dãy đã cho là tăng nghiêm ngặt. Dãy con rỗng không được tính vì điều đó ngụ ý rằng bạn đã không nhìn vào bất kỳ biển báo giới hạn tốc độ nào cả!

Ví dụ, \((1, 2, 5)\) là một dãy con tăng của \((1, 4, 2, 3, 5, 5)\), và chúng ta đếm nó hai lần vì có hai cách để chọn \((1, 2, 5)\) từ danh sách.

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. Dòng đầu tiên của mỗi bộ test chứa n, m, X, Y và Z cách nhau bởi một dấu cách. n sẽ là độ dài của dãy giới hạn tốc độ. m sẽ là độ dài của mảng tạo \(A\). m dòng tiếp theo sẽ chứa m phần tử của \(A\), mỗi dòng một số nguyên (từ \(A[0]\) đến \(A[m-1]\)).

Sử dụng \(A\), X, Y và Z, đoạn mã giả sau đây sẽ in ra dãy giới hạn tốc độ theo thứ tự. mod biểu thị phép toán lấy số dư.

for i = 0 to n-1
  print A[i mod m]
  A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

Lưu ý: Cách tạo dữ liệu vào không liên quan đến thuật toán tối ưu và chỉ tồn tại để giữ cho kích thước của các tệp dữ liệu vào ở mức thấp.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất một dòng chứa "Case #T: S" (ngoặc kép để cho rõ ràng) trong đó T là số thứ tự của bộ test và S là số lượng dãy con tăng nghiêm ngặt khác rỗng lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 20\)
• \(1 \le m \le 100\)
• \(0 \le X \le 10^9\)
• \(0 \le Y \le 10^9\)
• \(1 \le Z \le 10^9\)
• \(0 \le A[i] < Z\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le m \le n \le 1000\)
• Large dataset (Test set 2): \(1 \le m \le n \le 500000\)

Đ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
5 5 0 0 5
1
2
1
2
3
6 2 2 1000000000 6
1
2

Case #1: 15
Case #2: 13

Nguồn

Google Code Jam 2008, Vòng 1C, bài Increasing Speed Limits.

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