Опуклі пермутоміно

Поліміно - це зв'язна множина клітинок на клітчатій дошці. Поліміно називається опуклим, якщо кожен рядок та кожен стовбець поліміно є зв'язними. Наприклад, поліміно на картинці ($a$) є опуклим, а поліміно, зображене на картинці ($b$) не є опуклим.

Поліміно називається пермутоміно, якщо воно складається з 2 \cdot n вершин, усі його вершини мають координати від $1$ до $n$, і у ньому немає ні двох вертикальних відрізків з однаковою $x$-координатою, ні двох горизонтальних відрізків з однаковою $y$-координатою. Картинка нижче ілюструє пермутоміно з $14$ вершинами. Відмітимо, що це пермутоміно є опуклим.

Вам задано число $n$. Ваша задача полягає у тому, щоб порахувати кількість різних опуклих пермутоміно з 2 \cdot n вершинами. Два пермутоміно вважаються рівними, якщо їх можна накласти одне на інше, при цьому повороти та відображення не дозволяються.

Примітка

Пам'ятайте, що вам потрібно рахувати лише опуклі пермутоміно.