images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 19:42:45

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2065. Парад победы

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В честь уничтожения Звезды Смерти и победы над Империей, повстанцы устроили парад. В параде участвуют `n` человек. У каждого из них есть какое-то количество наград. Оказалось, что у каждых двух человек количество наград различно.
Организаторы парада ответственно отнеслись к его проведению. Участники парада по очереди выходят на площадь и строятся в линию. При этом, очередной выходящий проходит мимо всех уже стоящих на площади. Проходя мимо обладающего большим числом наград человека, проходящий обязан остановиться и отдать ему честь. На это уходит некоторое одинаковое, прописанное в уставе, время.
Во время подготовки все строго обговорили порядок, в котором будут стоять на площади. Но им стало известно, что на самом параде будет выставлена техника, которая загородит один из входов на площадь. К сожалению, ещё не известно будет ли загорожен левый или правый вход. Но, так как вся программа парада выверена до секунды, то, с какой стороны участники будут выходить на площадь, не должно сказаться на том, сколько времени им на это потребуется. Время, которое потребуется на то, чтобы выйти всем участникам, зависит только от количества раз, которое будет отдана честь.
Если будет закрыт правый выход, то люди будут выходить следующим образом: сначала тот, кто должен стоять левее всех, затем тот, кто должен стоять вторым, пройдя мимо уже стоящего первого, и так далее. Если же закрыт левый выход, то сначала выходит тот, кто будет стоять самым правым, затем тот, кто будет стоять вторым справа, проходя мимо уже стоящего правого, и так далее.
Интересными являются только те порядки построения, при которых время парада при выходе участников справа и слева будет одинаковым. Вам требуется определить их количество.
В единственной строке входного файла записано единственное целое число `n` (`1\ ≤\ n\ ≤\ 500`).
Выведите единственное число – количество способов, по модулю `10^9+7`.

Пример ввода 1

3

Пример вывода 1

0

Пример ввода 2

4

Пример вывода 2

6
Если количества наград у участников парада во втором примере равны числам `1`, `2`, `3` и `4`, то нас интересуют следующие порядки построения:
`1`, `4`, `3`, `2`
`2`, `3`, `4`, `1`
`2`, `4`, `1`, `3`
`3`, `1`, `4`, `2`
`3`, `2`, `1`, `4`
`4`, `1`, `2`, `3`
Источник: neerc.ifmo.ru/school
loading