Олимпиадный тренинг

Задача . A. Пишем код

Задача

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

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

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	3	1
2	24	3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет