2104: Засіб від нудьги
Переглянути як PDF
Надіслати розвʼязок
Бали:
100,00 (частково)
Ліміт часу:
3.0s
Ліміт памʼяті:
256M
Ввід:
stdin
Вивід:
stdout
Автор:
Тип задачі
Команда олімпійців вже впоралася з усіма задачами на турнірі, але додому йти ще рано, бо один з них запропонував розв'язати ще одну цікаву вправу на комбінаторику. Вони не змогли знайти рішення, тому вся надія на вас.
Необхідно визначити кількість можливих допустимих послідовностей карт для створення лінійної барикади в стилі розташування дужок довжини ~n~.
Наприклад, якщо ~n~ = 6, то існує 5 таких послідовностей.
{}{}{}
{}{{}}
{{}}{}
{{{}}}
{{}{}}
Формат вхідних даних
Єдине ціле число ~n~.
Формат вихідних даних
Відповідь на задачу - число по модулю ~10^9+7~
Обмеження
~1 \le n \le 10^6~
Sample input 1
6
Sample output 1
5
Коментарі
N може бути не парним?
так