В большом проекте программистам поступило задание: написать ровно m строчек кода. Над проектом работает n программистов, i-й из них допускает в каждой написанной им строчке кода ровно ai ошибок.
Назовем последовательность целых неотрицательных чисел v1, v2, ..., vn планом, если v1 + v2 + ... + vn = m. Программисты выполняют план следующим образом: сначала первый программист пишет первые v1 строк поставленного задания, потом второй программист пишет следующие v2 строк поставленного задания, и так далее. В конце, последний программист дописывает оставшиеся строчки кода. Назовем план хорошим, если в сумме все написанные строчки задания содержат не более b ошибок.
Ваша задача — определите, сколько существует различных хороших планов. Поскольку искомое количество планов может быть большим, выведите остаток от деления этого количества на число mod.
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю mod.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
7 9
1 4
2 8 2
0 4 1
8 9 3
|
4
2 1
|
|
2
|
1 1
0 0
1 1 10
|
0
|