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\).

Trên mặt phẳng tọa độ cho \(N\) hình vuông có các cạnh song song với các trục tọa độ. Các hình vuông được đánh số từ \(1\) đến \(N\), các đỉnh của hình vuông đều có tọa độ nguyên và không có hai hình vuông nào có điểm chung.

Một hình vuông được gọi là nhìn thấy được từ gốc tọa độ \(O=(0,0)\) nếu tồn tại hai điểm \(A\) và \(B\) trên cùng một cạnh của hình vuông sao cho phần trong của tam giác \(OAB\) không có điểm chung với bất kỳ hình vuông nào trong số các hình vuông còn lại.

Yêu cầu

Đếm số hình vuông nhìn thấy được từ gốc tọa độ.

Dữ liệu vào

Nhập từ stdin:

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 1000)\), là số lượng hình vuông.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa ba số nguyên \(x_i, y_i, L_i\) \((1 \le x_i, y_i, L_i \le 10000)\), cách nhau bởi dấu cách. Trong đó \((x_i,y_i)\) là tọa độ đỉnh ở góc dưới bên trái và \(L_i\) là độ dài cạnh của hình vuông thứ \(i\), với \(i=1,2,\ldots,N\).

Kết quả

In ra stdout một số nguyên là số lượng hình vuông nhìn thấy được từ gốc tọa độ.

Ví dụ 1

Input

3
2 6 3
1 4 1
3 4 1

Output

3

Ví dụ 2

Input

4
1 2 1
3 1 1
2 4 2
3 7 1

Output

2

"TextFile" là một virus chuyên tấn công các file văn bản theo phương thức sau: Sao chép một đoạn các ký tự liên tiếp trong nội dung của file văn bản vào bộ nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản.

Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự \(T\) và số nguyên không âm \(k\), xâu con gồm các ký tự từ vị trí \(p\) đến vị trí \(q\) của xâu \(T\) được gọi là đoạn có khả năng bị virus sao chép mức \(k\) nếu nó sai khác với xâu con gồm các ký tự từ vị trí \(q+1\) đến vị trí \(q+(q-p+1)\) của xâu \(T\) ở không quá \(k\) vị trí.

Ví dụ, xét xâu \(T = \texttt{zabaaxy}\) và \(k=1\). Đoạn văn bản \(\texttt{ab}\) từ ký tự thứ \(2\) đến ký tự thứ \(3\) là đoạn văn bản độ dài \(2\) có khả năng bị virus sao chép mức \(1\) vì nó khác với đoạn văn bản \(\texttt{aa}\) gồm các ký tự từ ký tự thứ \(4\) đến ký tự thứ \(5\) của xâu ở \(1\) vị trí.

Yêu cầu

Cho xâu \(T\) và \(n\) số nguyên không âm \(k_1, k_2, \ldots, k_n\). Với mỗi giá trị \(k_i\) (\(i=1,2,\ldots,n\)), hãy tìm độ dài đoạn dài nhất trong xâu \(T\) có khả năng bị virus sao chép ở mức \(k_i\).

Dữ liệu vào

Nhập từ bàn phím (standard input):

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 10\)).
• Dòng thứ hai chứa một xâu \(T\) gồm các chữ cái in thường lấy từ tập 26 chữ cái tiếng Anh từ a đến z.
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo ghi số nguyên không âm \(k_i\) (\(k_i \le 10\), \(i=1,2,\ldots,n\)).

Kết quả

In ra màn hình (standard output) \(n\) dòng, dòng thứ \(i\) ghi một số nguyên không âm là độ dài đoạn dài nhất có khả năng bị virus sao chép ở mức \(k_i\) (\(i=1,2,\ldots,n\)). Ghi \(0\) nếu không tìm được đoạn như vậy.

Giới hạn

Ký hiệu \(m\) là độ dài của xâu \(T\).

• Subtask 1 (40% số test tương ứng 40% số điểm): \(m \le 300\).
• Subtask 2 (30% số test tương ứng 30% số điểm): \(k_i = 0\) với mọi \(i\).
• Subtask 3 (30% số test tương ứng 30% số điểm): \(m \le 3000\).

Giới hạn thời gian: 3 giây/test. Giới hạn bộ nhớ: 256MB.

Ví dụ

Input 1

2
zabaaxy
0
1

1
2

Input 2

2
zcaabcaaaa
0
1

2
4

Giải thích (ví dụ 2): Đoạn dài nhất có khả năng bị virus sao chép ở mức \(0\) là \(\texttt{aa}\), có độ dài \(2\); đoạn dài nhất có khả năng bị virus sao chép ở mức \(1\) là \(\texttt{caab}\), có độ dài \(4\).