Задан набор неповторяющихся пар (A_i,A_j), A_i, A_j принадлежат множеству А={A₁, A₂, ..., A_n}.

Необходимо составить цепочку максимальной длины по правилу (A_i,A_j)+(A_j,Ak)=(A_i,A_j,A_k).

На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа A — особо опасные и типа B — неопасные. Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку (один над другим) для захоронения. Стопка является взрывоопасной, если в ней подряд идут более чем два контейнера с отходами типа A.

Требуется написать программу, которая подсчитывает количество возможных вариантов формирования взрывоопасной стопки для заданного числа контейнеров N.

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:
единственная строка входного файла содержит целое число N — количество контейнеров в стопке (1 <= N <= 31).

Формат выходных данных:
в единственной строке выходного файла должно содержаться искомое количество вариантов взрывоопасных стопок.

Перечислить все разбиения N на целые положительные слагаемые

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих? ...........

Найти максимальную по длине последовательность z, полученную вычеркиванием элементов как из x, так и из y.

Пусть x=x₁,x₂, ... ,x_m, y=y₁,y₂, ... ,y_n.

Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной