Крайній випадок
У теорії графів, парування або незалежна множина ребер у графі G = (V, E) — це множина ребер ME, така, що жодні два ребра в паруванні M не мають спільної вершини.
Нещодавно ви дізналися з новин, що "Премію Шведського національного банку з економічних наук пам'яті Альфреда Нобеля" (неофіційно, Нобелівська премія з економіки) за 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.