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

В честь уничтожения Звезды Смерти и победы над Империей, повстанцы устроили парад. В параде участвуют `n` человек. У каждого из них есть какое-то количество наград. Оказалось, что у каждых двух человек количество наград различно.

Организаторы парада ответственно отнеслись к его проведению. Участники парада по очереди выходят на площадь и строятся в линию. При этом, очередной выходящий проходит мимо всех уже стоящих на площади. Проходя мимо обладающего большим числом наград человека, проходящий обязан остановиться и отдать ему честь. На это уходит некоторое одинаковое, прописанное в уставе, время.

Во время подготовки все строго обговорили порядок, в котором будут стоять на площади. Но им стало известно, что на самом параде будет выставлена техника, которая загородит один из входов на площадь. К сожалению, ещё не известно будет ли загорожен левый или правый вход. Но, так как вся программа парада выверена до секунды, то, с какой стороны участники будут выходить на площадь, не должно сказаться на том, сколько времени им на это потребуется. Время, которое потребуется на то, чтобы выйти всем участникам, зависит только от количества раз, которое будет отдана честь.

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

Интересными являются только те порядки построения, при которых время парада при выходе участников справа и слева будет одинаковым. Вам требуется определить их количество.

В единственной строке входного файла записано единственное целое число `n` (`1\ ≤\ n\ ≤\ 500`).

Выведите единственное число – количество способов, по модулю `10^9+7`.

3

0

4

6

Если количества наград у участников парада во втором примере равны числам `1`, `2`, `3` и `4`, то нас интересуют следующие порядки построения: