Числа Фібоначчі задаються формулами \(F(1) = 1, F(2) = 1, F(i) = F(i-1) + F(i-2)\)

Потрібно порахувати останні ТРИ цифри \(N\)-го числа Фібоначчі.

Формат вхідних даних

У першому рядку вхідного файлу міститься натуральне число \(N\) (\(1 \le n \le 10^{18})\)

Формат вихідних даних

Перший рядок вихідного файлу повинен містити єдине число - відповідь до задачі.

Приклад вхідних даних-1

7

Приклад вихідних даних-1

13

Приклад вхідних даних-2

20

Приклад вихідних даних-2

765

Приклад вхідних даних-3

25

Приклад вихідних даних-3

025