← К списку задач

Вежливые люди

Сложность: 36%

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

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

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

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

В первой строке дано единственное целое число nn (11018)(1 \le 10^{18}) – количество мест в ряду.

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

Выведете единственное число — количество возможных перестановок зрителей. Так как ответ может быть достаточно большим, выведите его по модулю 109+910^9 + 9.

Подзадачи

баллынеобх. подзадачиограничения
1

15

-

n50n \le 50

2

35

1

n105n \le 10^5

3

50

1, 2

n1018n \le 10^{18}

STDINSTDOUT
1
1
3
4