2390 год. В заброшенном метрополитене города N-ска завелась громадная змея-мутант. Она ползает вдоль перегонов между станциями, повергая в ужас случайно забредающих под землю потомков людей. Размеры змеи настолько велики, что иногда голова появляется на той станции, вдоль которой еще ползет какая-то другая часть тела, и змея повергает в ужас сама себя. Чтобы избавиться от этой проблемы, змея поймала вас и потребовала написать для нее программу, которая может ей прокладывать кратчайший маршрут для головы от одной станции до другой, не проползая при этом по станциям, где находятся участки ее тела.

Будем называть маршрутом последовательность станций, каждые две последовательные из которых соединены перегоном.

Все перегоны в метрополитене имеют одинаковую длину, а змея имеет длину в \((l - 0.5)\) перегонов. Змея может ползти вдоль перегонов, переползая с одного на другой на станциях. Змея может ползти вдоль перегона только в один слой, а ее голова не может появляться на станции, если в этот момент по станции проползает другая часть ее тела. Змея умеет ползать только головой вперед.

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

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

На барже располагается K грузовых отсеков. В каждый отсек можно поместить некоторое количество бочек с одним из 10 000 видов топлива. Причём извлечь бочку из отсека можно лишь в случае, если все бочки, помещённые в этот отсек после неё, уже были извлечены. Таким образом в каждый момент времени в каждом непустом отсеке имеется ровно одна бочка, которую можно извлечь не трогая остальных. Будем называть такие бочки крайними.

Изначально баржа пуста. Затем она последовательно проплывает через N доков, причём в каждом доке на баржу либо погружается бочка с некоторым видом топлива в некоторый отсек, либо выгружается крайняя бочка из некоторого отсека. Однако, если указанный отсек пуст, либо если выгруженная бочка содержит не тот вид топлива, который ожидалось, следует зафиксировать ошибку. Если на баржу оказывается погружено более P бочек или если после прохождения всех доков она не стала пуста, следует также зафиксировать ошибку. От вас требуется либо указать максимальное количество бочек, которые одновременно пребывали на барже либо зафиксировать ошибку.

По данному натуральному n определите количество последовательностей длины n из 0 и 1, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 2³¹-1.

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 2³¹-1.

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд и двух двоек подряд. Гарантируется, что ответ не превосходит 2³¹-1.