Viết Code

Một nhóm $n$ lập trình viên cần viết đúng $m$ dòng code. Lập trình viên thứ $i$ tạo ra đúng $a_i$ lỗi (bug) trên mỗi dòng code mà mình viết.

Một kế hoạch là một dãy số nguyên không âm $v_1,v_2,\dots ,v_n$ với $v_1+v_2+\dots +v_n=m$. Theo kế hoạch này, lập trình viên thứ $1$ viết $v_1$ dòng đầu, lập trình viên thứ $2$ viết $v_2$ dòng tiếp theo, và cứ thế cho đến hết.

Một kế hoạch được gọi là tốt nếu tổng số lỗi trên toàn bộ $m$ dòng code không vượt quá $b$.

Hãy đếm số kế hoạch tốt phân biệt, kết quả lấy dư cho số nguyên dương $\text{mod}$ cho trước.

Hai kế hoạch $(v_1,\dots ,v_n)$ và $(v_1^{\prime },\dots ,v_n^{\prime })$ được coi là khác nhau nếu tồn tại chỉ số $i$ sao cho $v_i\ne v_i^{\prime }$.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $b$, $\text{mod}$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất — số kế hoạch tốt, lấy dư cho $\text{mod}$.

Ràng buộc

• $1\le n,m\le 500$
• $0\le b\le 500$
• $1\le \text{mod}\le {10}^9+7$
• $0\le a_i\le 500$

Ví dụ