Codeforces Round 302 (Div. 1) |
---|
Закончено |
В большом проекте программистам поступило задание: написать ровно 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
Название |
---|