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