Числа Фибоначчи – элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …, в которой каждое последующее число равно сумме двух предыдущих чисел.
Имеются натуральные числа N и М. Числа Фибоначчи, находящиеся в диапазоне [ N, M ], записываются подряд без пробелов. В полученной последовательности на позиции с номером, равным половине длины последовательности, находится некоторая цифра. Для последовательностей с нечетным количеством цифр половину длины необходимо вычислять с округлением до ближайшего большего целого.
Например, для N = 10 и М = 100 последовательность выглядит как 1321345589. Длина последовательности составляет 10 цифр, середина последовательности 5 и на пятой позиции стоит цифра 3.
Для N = 5 и М = 200 последовательность выглядит как 581321345589144. Длина последовательности составляет 15 цифр, середина последовательности 7,5 (округляем до 8) и на 8 позиции стоит цифра 4.
Тогда для чисел N = 111 и М = 20396847 на позиции в середине последовательности находится цифра …