Выпуклые пермутомино

Полимино - это связное множество клеточек на клетчатой доске. Полимино называется выпуклым, если каждая строка и каждый столбец полимино являются связными. Например, полимино на картинке (a) является выпуклым, а полимино, изображённое на картинке (b) не является выпуклым.

Полимино называется пермутомино, если оно состоит из 2·n вершин, все его вершины имеют координаты от 1 до n, и в нём нет ни двух вертикальных отрезков с одинаковой x-координатой, ни двух горизонтальных отрезков с одинаковой y-координатой. Картинка ниже иллюстрирует пермутомино с 14 вершинами. Заметим, что это пермутомино является выпуклым.

Вам дано число n. Ваша задача состоит в том, чтобы посчитать количество различных выпуклых пермутомино с2·n вершинами. Два пермутомино считаются равными, если их можно наложить одно на другое, при этом повороты и отражения не разрешаются.

Входные данные

Единственное число n (2 ≤ n ≤ 30).

Выходные данные

Одно число - количество выпуклых пермутомино с 2·n вершинами.

Примеры

Примечание

Помините, что вам следует считать только выпуклые пермутомино.