22090번 - Конструктор пил 다국어

Иван — конструктор пил. Целью конструктора пил является формирование профиля пилы — длин зубьев. Ведь пила с различным размером зубьев пилит гораздо лучше, чем пила с одинаковыми размерами зубьев.

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

• размеры всех зубьев пилы различны,
• второй зуб пилы больше, чем первый и третий,
• четвертый зуб пилы больше, чем третий и пятый,
• ...

То есть фактически размеры зубьев должны образовывать перестановку, причем зубья, которые стоят на чётных позициях, должны быть больше своих соседей.

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

Например, из четырех зубьев Ивана может составить 5 различных пил: (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3) и (3, 4, 1, 2).

В первой и единсивенной строке содержится целое число n — количество зубьев в пиле, которую хочет сделать Иван (1 ≤ n ≤ 5 000).

Выведите искомое количество пил по модулю 10⁹ + 7.