Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнееиз этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.

Треугольник Паскаля – это бесконечный треугольник из чисел, который имеет следующий вид:

Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число – единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.

Таким образом, \(i\)-ая строка содержит \(i\) + 1 число. Если обозначить \(j\)-ый элемент \(i\)-ой строки как \(a_i\),\(j_,\) то выполняется равенство \(a_i\),\(j\) = \(a_i\) - 1,\(j\) - 1 + \(a_i\)-1,\(j\). Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами -1 и \(i\)) равными нулю.

Коля хочет узнать, сколько нечетных чисел в n-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.

Известны первые \(k\) членов последовательности – \(a_1, a_2, \dots, a_k\) (\(0 \leq a_i \leq 9\), где \(i = 1, 2, \dots, k\)). Другие члены последовательности вычисляются по следующему правилу: \(a_i = \sum_{j=i-k}^{i-1}a_j\), то есть каждый следующий член равен сумме \(k\) предыдущих. Необходимо найти последние \(r\) цифр числа \(a_n\).

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи. Строки Фибоначчи определяются следующим образом:

• f ₀ = a
• f ₁ = b
• f _n = f _{n −1} f _{n −2} для каждого n ≥ 2 — конкатенация двух предыдущих строк Фибоначчи

Аллу сразу заинтересовал вопрос — какой максимально длинный палиндром встречается в k -й строке Фибоначчи. Помогите Алле решить эту задачу.