I. Insidious time limit
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тимур и Ерулан, готовясь к олимпиаде, нашли старую задачу. Путь к вершине спортивного программирования нелёгок, и пока у них не всё получается, что случилось и с этой задачей. Уже который раз подряд они получают вердикт TL на 20 тесте. Может, получится у вас? Вот сама проблема: найти $$$a_n$$$, где $$$a_k = a_{k-2} + a_{k-3}$$$ для всех $$$k$$$, начиная с 3.

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

Две строки: на первой строке одно целое число $$$n$$$ (от $$$0$$$ до $$$10^{18}$$$), на второй строке три целых числа $$$a_0$$$, $$$a_1$$$, $$$a_2$$$ (от 0 до $$$10^{18}$$$).

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

Одно целое неотрицательное число $$$a_n$$$ — ответ по модулю $$$10^9$$$.

Примеры
Входные данные
3
10 11 12
Выходные данные
21
Входные данные
0
5 11 20
Выходные данные
5