Cho một mảng gồm số nguyên dương. Chúng ta cần xây dựng một dãy chỉ số có độ dài , trong đó mỗi phần tử là một số nguyên thỏa mãn .
Từ dãy chỉ số , ta tính giá trị tổng hợp theo công thức trọng số cơ số 10 như sau:
(Tức là: ).
Hãy đếm số lượng dãy chỉ số thỏa mãn điều kiện: .
Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên được phân tách bằng dấu cách: và () — số lượng phần tử của mảng , độ dài dãy chỉ số cần xây dựng, phần dư mục tiêu và số chia modulo.
Dòng tiếp theo chứa số nguyên () được phân tách bằng dấu cách — các phần tử của mảng .
Kết quả:
In ra một số nguyên duy nhất là số lượng dãy chỉ số thỏa mãn yêu cầu bài toán, modulo .
Ví dụ:
Dữ liệu:
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
Kết quả:
3
Dữ liệu:
3 2 1 2
6 2 2
Kết quả:
0
Dữ liệu:
3 2 1 2
3 1 2
Kết quả:
6
Giải thích: Trong ví dụ thứ ba:
Mảng . Cần xây dựng dãy độ dài .
Các giá trị có thể tạo thành từ các cặp chỉ số là:
Có tổng cộng 6 trường hợp chia 2 dư 1.
Giới hạn:
Subtask 1 (20% số điểm): .
Subtask 2 (20% số điểm): .
Subtask 3 (20% số điểm): .
Subtask 4 (40% số điểm): Không có ràng buộc bổ sung.
