Ограничение по времени выполнения 1 секунда Ограничение по использованию памяти 128 мегабайт Функция f(n) задана рекуррентным соотношением:
Найдите значение f(n) mod 123456789.
Входные данные
Одно натуральное число n (1≤n≤109).
Выходные данные
Выведите значение f(n) mod 123456789.
Примеры