АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1335. Embroidery

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

A long band of fabric is about to be embroidered with a geometric pattern. The horizontally-oriented band is marked with a 1´n guiding grid. The pattern is made according to the following rules.

1.     The pattern starts in the lower left corner.

2.     Every stitch connects two corners of a square in the guiding grid. The stitch may go in any direction: vertical, horizontal, or diagonal.

3.     The fabric may be punctured only at the corners of grid squares, and only once for each corner. The final pattern must use all the corners.

4.     The embroidery is done with a single continuous thread starting in the lower left corner of the grid and ending in any corner of any square.

 

Your task is to write a program that determines the number of different ways to embroider a band of size 1´n.

The figure below demonstrates all the 20 ways to embroider a 1´2 band according to the above rules. Front and back stitches are shown with lines of different thickness.

 

Limitations

1 £ n £ 30.

Input

The input file contains a single integer n.

Output

The output file should contain a single integer, the number of possible designs.

 

Example

Input

Output

1

6

2

20

3

72

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1334. J - Dominoes 1335.
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.