Ta định nghĩa trọng số của một dãy ~b_1, b_2, ..., b_k~, ký hiệu là ~W(b)~, theo công thức sau:

$$W(b) = (b_1 + b_2 + \dots + b_k) \mod m$$

Xét một dãy số nguyên dương ~a_1, a_2, ..., a_n~. Đếm số dãy con ~b~ có độ dài ~k~ của ~a~ có ~W(b) = x~.

Nhắc lại, một dãy ~b~ được gọi là dãy con của một dãy ~a~ khi và chỉ khi tồn tại một cách xóa một số phần tử của ~a~ và giữ nguyên thứ tự các phần tử còn lại để tạo thành dãy ~b~.

Dữ liệu

• Dòng đầu tiên gồm bốn số nguyên dương ~n, k, m, x~ ~(1 \le n \le 800, 1 \le k \le 6, 0 \le x < m \le 2 \times 10^7)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^9)~.

Kết quả

• Một dòng duy nhất gồm số dãy con thỏa mãn.

Subtask

Ví dụ

Ví dụ 1

Dữ liệu

5 2 2 0
1 2 3 4 5

Kết quả

4

Giải thích

• Các dãy con thỏa mãn là: ~(1, 3), (3, 5), (1, 5), (2, 4)~.

Ví dụ 2

Dữ liệu

5 3 2 1
1 2 3 4 5

Kết quả

4