Рекуррентные последовательности

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

Входные данные
Вводится одно число N (0<=N<=30).

Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + 1 (n>0),
a_2n+2 = a_2n+1 - a_n (n>0),
a₀=1, a₁=1.

Входные данные
Вводится натуральное число n, не превосходящее 1000.

Выходные данные
Выведите ответ к задаче.

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + a_n-1,
a_2n+1 = a_n – a_n-1,
a₀ = a₁ = 1.

Входные данные
Вводится одно натуральное число n (1≤n≤1000).

Выходные данные
Вывести одно число a_n.

Последовательность чисел Фибоначчи определяется следующим образом: F₀ = F₁ = 1,

F_n+1 = F_n+F_n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.

Входные данные
В единственной строке входных данных записано натуральное число n (1≤n≤1000).

Выходные данные
Вывести последнюю цифру числа F_n.

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

Входные данные
В первой строке находятся числа a₁ и N, разделённые пробелом.

Выходные данные
Вывести одно число - a_N.

Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Ограничения: длина S от 1 до 25, 1 <= N <= 45.

Примечание. Длина F(45) равна 1 134 903 170.

Входные данные
В первой строке содержится число N, во второй - строка S.

Выходные данные
Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).

Рассмотрим неубывающую последовательность s₁, ..., s_n + 1 ( s_i <= s_i + 1 для 1 <= i <= n ). Последовательность m₁, ..., m_n, в которой каждый член определен как m_i = ½ * ( s_i + s_i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s₁, ... s_n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s₁, ..., s_n + 1, для которых заданная последовательность m₁, ..., m_n является средней последовательностью.

Задание
Напишите программу, которая:

• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.

Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m₁, ..., m_n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).

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

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами x_i и y_i (0≤x_i,y_i≤10⁴).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p₁,p₂,…,p_N из N точек
Она рисует отрезки между p₁ и p₂, p₂ и p₃, p₃ и p₁.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от p_i до p_j для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10⁹+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x_i и y_i.

Выходные данные: 
Количество перестановок по модулю 10⁹+7.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 4 1 1 1 2	0	Никакая перестановка не сработает.
2	4 0 0 0 4 4 0 1 1	24	Все перестановки работают.
3	5 0 0 0 4 4 0 1 1 1 2	96	Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1). Для этой перстановки Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0). Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2). Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1). Рисунок: Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.