Một bài toán trong đại hội Toán-Tin của Thiên hà như sau: Xét các số nguyên dương có dạng \(a_1a_2...a_n\) , trong đó \(a_i\) nhận giá trị \(1\) từ đến \(k\) . Một đoạn chữ số từ vị trí thứ \(L\) đến vị trí thứ \(L + 9\) được gọi là đoạn hoàn hảo nếu:

1) \(a_L + a_{L + 1} + ... + a_{L + 9} = 20\);
2) Các chữ số \(a_L, a_{L + 1}, ..., a_{L + 9}\) có thể chia làm \(2\) nhóm có tổng bằng nhau.

Yêu cầu: Cho \(n, k\) và \(m\) vị trí \(p_1, p_2,..., p_m\), hãy đếm số lượng số nguyên dương có dạng \(a_1a_2...a_n\) (\(a_i\) nhận giá trị từ \(1\) đến \(k\)) mà có \(m\) đoạn hoàn hảo lần lượt bắt đầu từ \(p_1, p_2,..., p_m\).

Input

Vào từ thiết bị vào chuẩn:

• Dòng đầu gồm bốn số nguyên dương \(n, k, m, D\) \((9 < n \le 50; k \le 9; D \le 10^9)\).
• Dòng thứ hai gồm \(m\) số nguyên \(p_1, p_2,..., p_m\) \((1 \le p_1 < p_2 < \dots < p_m \le n - 9)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên \(r\), trong đó \(r\) là phần dư của số lượng số thỏa mãn chia cho \(D\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m = 1\);
• Subtask \(2\) (\(20\%\) số điểm): \(m = 2\);
• Subtask \(3\) (\(60\%\) số điểm): \(m \le 5\).

Example

15 2 2 123
1 3

8