Опуклі пермутоміно
Поліміно - це зв'язна множина клітинок на клітчатій дошці. Поліміно називається опуклим, якщо кожен рядок та кожен стовбець поліміно є зв'язними. Наприклад, поліміно на картинці (a) є опуклим, а поліміно, зображене на картинці (b) не є опуклим.
Поліміно називається пермутоміно, якщо воно складається з 2·n вершин, усі його вершины мають координати від 1 до n, і у ньому немає ні двох вертикальних відрізків з однаковою x-координатою, ні двох горизонтальних відрізків з одинаковою y-координатою. Картинка нижче ілюструє пермутоміно з 14 вершинами. Відмітимо, що це пермутоміно є опуклим.
Вам задано число n. Ваша задача полягає у тому, щоб порахувати кількість різних опуклих пермутоміно з 2·n вершинами. Два пермутоміно вважаються рівними, якщо їх можна накласти одне на інше, при цьому повороти та відображення не дозволяються.
Вхідні дані
Єдине число n (2 ≤ n ≤ 30).
Вихідні дані
Одне число - кількість опуклих пермутоміно з 2·n вершинами.
Примітка
Пам'ятайте, що вам потрібно рахувати лише опуклі пермутоміно.
