Крайний случай
В теории графов сочетание или независимое множество рёбер в графе G = (V, E) — это такое множество рёбер ME, в котором никакие два ребра не имеют общую вершину.
Недавно вы узнали из новостей, что "Премия Шведского государственного банка по экономическим наукам памяти Альфреда Нобеля" (неофициально, Нобелевская премия по экономике) за 2012 год была вручена Элвину Э. Роту и Ллойду С. Шепли за их алгоритм нахождения сочетания, удовлетворяющего определённым критериям в двудольном графе. Поскольку вы также слышали, что сочетания в циклических графах находят применение в химии, ваши мысли сосредоточены на будущем, где ваши рождественские покупки будут более роскошными, чем когда-либо!
Циклический граф, C_n, n ≥ 3, — это простой неориентированный граф с множеством вершин {1, ..., n} и множеством рёбер E(Cn) = {(a, b) | |a-b|≡1 mod n}. Он 2-регулярный и содержит n рёбер. Графы C_3, C_4, C_5 и C_6 показаны на Рисунке 1.
Рисунок 1: Графы C_3, C_4, C_5 и C_6.
Ваш первый шаг к славе Нобелевской премии — научиться вычислять количество сочетаний в циклическом графе C_n. На Рисунке 2 представлены семь сочетаний графа C_4.
Рисунок 2: Сочетания C_4. Рёбра, входящие в соответствующее сочетание, окрашены в зелёный цвет, а рёбра, не входящие в сочетание, изображены пунктиром. M_1 = Ø, M_2 = {{2, 1}}, M_3 = {{3, 2}}, M_4 = {{4, 3}}, M_5 = {{1, 4}}, M_6 = {{2, 1},{4, 3}}, и M_7 = {{3, 2},{1, 4}}.
Входные данные
Для каждого теста вы получаете одну строку, содержащую одно положительное целое число: n, где 3 ≤ n ≤ 10000.
Выходные данные
Для каждого теста выведите строку, содержащую количество сочетаний в C_n.