Тренировка на динамическое программирование

Соревнование завершилось 26.01.18 в 22:00

A. Глупый Шахматный Король

Автор задачи: Хаустов Павел
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Имеется шахматная доска размером N × N клеток. В нижней левой клетке стоит редкая шахматная фигура — «Глупый король», которая может перемещаться только на соседнюю справа или сверху клетку.

Очевидно, что «Глупый король» имеет конечное количество способов добраться из левой нижней клетки доски в правую верхнюю, не поднимаясь выше побочной диагонали. Ваша задача — посчитать это количество для заданного значения N.

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

Единственная строка входных данных содержит целое число N (1 ≤ N ≤ 20).

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

Единственная строка выходных данных должна содержать единственное число — количество способов «Глупому королю» добраться из левой нижней клетки доски в правую верхнюю, не поднимаясь выше побочной диагонали.

Примеры
Стандартный вводСтандартный вывод
11
32