Задача Street

У місті Нью-Петрики побудували нову вулицю. Будинки поставили в одну лінію, а не в дві – не змогли дійти згоди про ширину проїжджої частини… Перший будинок мав 1 поверх, другий – 2 і т.д., тобто в кожному наступному будинку поверхів на один більше, ніж в попередньому. Для покращення зовнішнього вигляду фасади будинків  вирішили пофарбувати – кожен поверх в свій колір. Але, як водиться, фарбу купили лише 2-х кольорів – білу і червону. Мер вирішив, що 2 білі поверхи в одному будинку може бути підряд,  а ось 2 червоні – ні. Зрозуміло, що будь який будинок можна розфарбувати (кожен поверх в свій колір) не одним способом. Програмісту Хакерову доручили порахувати кількість способів фарбування для кожного з достатньо великої кількості будинків вулиці. Його програма вивела на принтер послідовно кількість способів для кожного будинку від першого до останнього без пропусків (помилився з форматом Виведення, таке в нього вже було на першому турі  NetOI). Вийшов чималий рядок цифр. Допоможіть Хакерову знайти N-ту цифру в цьому рядку (зрозуміло, що цифра з номером N є в роздруківці).
Технічні умови.  Програма  Street читає з клавіатури єдине число N (1 ≤ N ≤ 10000000) – номер цифри в послідовності і виводить на екран єдине число – шукану величину.
Приклади