Задача Street

В городе Нью-Петрики построили новую улицу. Дома поставили в одну линию, а не в две – не смогли прийти к согласию о ширине проезжей части. Первый дом имел 1 этаж, второй – 2 и т.д., то есть в каждом следующем доме этажей на один больше, чем в предыдущем. Для улучшения внешнего вида фасады домов  решили покрасить – каждый этаж в свой цвет. Но как водится, краску купили лишь 2-х цветов – белую и красную. Мэр решил, что 2 белых этажа в одном доме могут быть  подряд,  а вот 2 красных – нет. Понятно, что любой из домов  можно раскрасить (каждый этаж в свой цвет) не единственным способом. Программисту Хакерову поручили посчитать количество способов окрашивания для каждого из достаточно большого количества домов улицы. Его программа вывела на принтер последовательно количество способов для каждого дома от первого до последнего без пропусков (ошибся с форматом выведения, такое у него уже было на первом туре  NеtOI). Вышла достаточно большая строка цифр. Помогите Хакерову найти N-ую цифру в этой строке (понятно, что цифра с номером N есть в распечатке).

Технические условия. Программа Street читает с клавиатуры единственное число N (1 ≤ N ≤ 10000000) – номер цифры в последовательности и  Выводит на экран единственное число – искомую величину.