A. Пишем код
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В большом проекте программистам поступило задание: написать ровно m строчек кода. Над проектом работает n программистов, i-й из них допускает в каждой написанной им строчке кода ровно ai ошибок.

Назовем последовательность целых неотрицательных чисел v1, v2, ..., vn планом, если v1 + v2 + ... + vn = m. Программисты выполняют план следующим образом: сначала первый программист пишет первые v1 строк поставленного задания, потом второй программист пишет следующие v2 строк поставленного задания, и так далее. В конце, последний программист дописывает оставшиеся строчки кода. Назовем план хорошим, если в сумме все написанные строчки задания содержат не более b ошибок.

Ваша задача — определите, сколько существует различных хороших планов. Поскольку искомое количество планов может быть большим, выведите остаток от деления этого количества на число mod.

Входные данные

В первой строке записано четыре целых числа n, m, b, mod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — количество программистов, количество строчек кода в задании, максимальное возможное суммарное количество ошибок и модуль, который вы должны использовать при выводе ответа.

В следующей строке записано n целых чисел через пробел a1, a2, ..., an (0 ≤ ai ≤ 500) — сколько ошибок на строку допускает каждый из программистов.

Выходные данные

Выведите единственное целое число — ответ на задачу по модулю mod.

Примеры
Входные данные
3 3 3 100
1 1 1
Выходные данные
10
Входные данные
3 6 5 1000000007
1 2 3
Выходные данные
0
Входные данные
3 5 6 11
1 2 1
Выходные данные
0