Một nhóm lập trình viên đang làm một dự án lớn và vừa nhận được nhiệm vụ viết đúng \(m\) dòng mã. Có \(n\) lập trình viên tham gia dự án, trong đó người thứ \(i\) mắc đúng \(a_i\) lỗi (bug) trên mỗi dòng mã mà anh ta viết.

Gọi dãy gồm \(n\) số nguyên không âm \(v_1, v_2, \ldots, v_n\) là một kế hoạch nếu \(v_1 + v_2 + \ldots + v_n = m\). Các lập trình viên thực hiện nhiệm vụ theo kế hoạch như sau:

• Đầu tiên, lập trình viên thứ nhất viết \(v_1\) dòng mã đầu tiên của nhiệm vụ.
• Sau đó, lập trình viên thứ hai viết tiếp \(v_2\) dòng mã.
• Cứ như vậy, cuối cùng lập trình viên thứ \(n\) viết nốt phần còn lại gồm \(v_n\) dòng.
  Một kế hoạch được gọi là tốt nếu tổng số lỗi của tất cả \(m\) dòng mã không vượt quá \(b\), tức là:

Hai kế hoạch được coi là khác nhau nếu tồn tại ít nhất một chỉ số \(i\) mà giá trị \(v_i\) của hai kế hoạch khác nhau.

Yêu cầu

Hãy đếm số kế hoạch tốt phân biệt. Vì số lượng kế hoạch có thể rất lớn, hãy in ra phần dư của số đó khi chia cho số nguyên dương \(mod\) cho trước.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên \(n, m, b, mod\) (\(1 \le n, m \le 500\); \(0 \le b \le 500\); \(1 \le mod \le 10^9 + 7\)) lần lượt là số lập trình viên, số dòng mã của nhiệm vụ, tổng số lỗi tối đa cho phép và số nguyên dùng để lấy phần dư khi in đáp án.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 500\)) cách nhau bởi dấu cách, là số lỗi trên mỗi dòng mã của từng lập trình viên.

Dữ liệu ra

In ra một số nguyên duy nhất là số kế hoạch tốt, lấy phần dư khi chia cho \(mod\).

Ví dụ

Input 1

3 3 3 100
1 1 1

Output 1

10

Input 2

3 6 5 1000000007
1 2 3

Output 2

0

Giải thích

• Ví dụ 1: Có 3 lập trình viên, mỗi dòng mã có đúng 1 lỗi và cần viết 3 dòng, nên mọi kế hoạch đều có đúng 3 lỗi (không vượt quá \(b = 3\)). Do đó mọi kế hoạch đều tốt. Số kế hoạch là số nghiệm nguyên không âm của \(v_1 + v_2 + v_3 = 3\), bằng \(\binom{5}{2} = 10\).
• Ví dụ 2: Mỗi dòng mã có ít nhất 1 lỗi, mà cần viết 6 dòng nên tổng số lỗi luôn \(\ge 6 > b = 5\). Không có kế hoạch nào tốt, đáp án là \(0\).