G. Кубики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вероника любит играть в свои игрушки. Кубики – одни из её самых любимых игрушек.

Вероника складывает из разноцветных кубиков башенки, пирамидки и многие другие фигуры. Сегодня Вероника хочет построить башенку из $$$n$$$ кубиков в высоту. У Вероники есть кубики красного, зелёного и синего цвета в неограниченном количестве. Вероника хочет построить красивую разноцветную башенку, поэтому она хочет, чтобы в башне было не более $$$k_r$$$ подряд красных кубиков, $$$k_g$$$ подряд зелёных кубиков и $$$k_b$$$ подряд синих кубиков.

Помогите Веронике определить, сколько различных башенок высотой $$$n$$$ кубиков она сможет построить. Так как это число может оказаться очень большим, выведите ответ по модулю $$$10^9 + 7$$$.

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

В единственной строке содержатся четыре целых числа $$$n$$$, $$$k_r$$$, $$$k_g$$$, $$$k_b$$$ $$$(1\leq n,k_r,k_g,k_b\leq 10^6)$$$  — высота башни и ограничения по количеству подряд идущих красных, зелёных и синих кубиков соответственно.

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

В единственной строке выведите целое число – количество различных вариантов башенок, взятое по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
5 2 2 2
Выходные данные
180
Входные данные
6 1 1 3
Выходные данные
222
Входные данные
3 1 1 1
Выходные данные
12
Входные данные
4 4 4 4
Выходные данные
81