2-й этап Всеукраинской олимпиады по информатике 2013-2014 уч.г. 10 кл. г. Бердичев
А чем Миша хуже Васи и Даши?
Миша где-то вычитал, что такое цифровой корень числа: "Если мы сложим все цифры какого-либо числа, затем все цифры найденной суммы и будем повторять это много раз, мы, наконец, получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 34697 равен 2 (3+4+6+9+7=29; 2+9=11; 1 + 1=2)."
Миша ввёл своё понятие: цифровой корень 4-го порядка - это описанный выше цифровой корень, но находится он по последним 4-м цифрам числа. Поэтому цифровой корень 4-го порядка для числа из примера выше равен 8.
Помогите Мише найти цифровой корень 4-го порядка k-го числа Фибоначчи.
Напомним, что числа Фибоначчи определяются следующими рекуррентными соотношениями:
Input data
В каждой строке входного файла задано единственное число k (0 ≤ k ≤ 9223372036854775807).
Output data
Для каждого примера входных данных выведите в отдельной строке единственное число - ответ на поставленную задачу.
Examples
0 1 2 37 14 135 23
1 1 2 6 7 3 5