Сложность: 36%
Театр — это место, в котором собираются очень вежливые люди. Люди на столько вежливые, что при посадке на своё место они не готовы переходить через другого уже сидящего человека.
Ряд в театре представляет из себя мест, к которым есть проход с обоих сторон ряда. Вам необходимо посчитать количество возможных перестановок зрителей, в котором они могут начать занимать свои места так, чтобы им не пришлось переходить через уже сидящих людей.
Будем считать, что вежливые зрители начинают занимать места строго в порядке заданной перестановки; каждый из них начинает идти сразу после того, как предыдущий человек занял своё место.
Входные данные
В первой строке дано единственное целое число – количество мест в ряду.
Выходные данные
Выведете единственное число — количество возможных перестановок зрителей. Так как ответ может быть достаточно большим, выведите его по модулю .
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 15 | - | |
2 | 35 | 1 | |
3 | 50 | 1, 2 |
STDIN | STDOUT |
1 | 1 |
3 | 4 |