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