eolymp
bolt
Try our new interface for solving problems
Problems

Даша тоже фибоначчит

Даша тоже фибоначчит

Time limit 0.5 seconds
Memory limit 64 MiB

- Мам, а мам, а почему на часах

каждая четверть имеет 15 минут?

- Спроси об этом у Васи, говорят,

он спрашивал об этом у Фибоначчи,

а я тоже на работу опаздываю!

Из утреннего разговора

дочери с матерью

Девятиклассница Даша на год старше восьмиклассника Васи, и она тоже экспериментирует с числами Фибоначчи. Так как она старше, то и задачки решает посложнее. В данный момент её интересует ответ на вопрос: как быстро найти произведение 3-х последних цифр k-го числа Фибоначчи? В отличие от Васи, если цифр не хватает, то Даша не дописываает спереди ничего не значащие в данном случае ведущие нули.

Напомним, что числа Фибоначчи определяются следующими рекуррентными соотношениями:

Дашу параллельно также волнуют иные вопросы: Почему так ответила мама и связан ли её ответ с решаемой на данный момент задачей? Да и связан ли вообще?

Input data

В каждой строке входного файла задано единственное число k (0k9223372036854775807).

Output data

Для каждого примера входных данных выведите в отдельной строке единственное число - ответ на поставленную задачу.

Examples

Input example #1
0
1
2
37
14
135
23
Output example #1
1
1
2
54
0
56
144
Author Анатолий Присяжнюк
Source 2-й этап Всеукраинской олимпиады по информатике 2013-2014 уч.г. 9 кл. г. Бердичев