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