ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1946. Китайский хоккей 3

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В высшей лиге чемпионата КНР по настольному хоккею участвуют n лучших игроков со всех уголков галактики, колонизированных республикой. В течение сезона каждый участник лиги должен сыграть с каждым ровно один матч. Игра ведётся до тех пор, пока не будут забиты ровно 3 гола. Таким образом, в настольном хоккее не бывает ничьих — все матчи заканчиваются либо со счётом 3:0, либо со счётом 2:1 в пользу одного из игроков. В итоговой таблице результатов лиги игроки упорядочиваются по суммарному количеству забитых ими во всех встречах голов.
Вы работаете в букмекерском агентстве, которое принимает прогнозы на итоговый вид таблицы результатов. Для победы в конкурсе прогнозов необходимо абсолютно точно назвать количество голов, забитых победителем, количество голов, забитых игроком, занявшим второе место, и так далее, вплоть до количества голов, забитых игроком, занявшим последнее место. При этом угадывать имена игроков не нужно. Помогите агентству посчитать количество всевозможных прогнозов.

Исходные данные

В единственной строке записано целое число n (2 ≤ n ≤ 50).

Результат

Выведите количество возможных прогнозов на итоговые результаты, взятое по модулю 109 + 7.

Пример

исходные данныерезультат
3
8

Замечания

Для трёх игроков возможны следующие прогнозы: (6, 3, 0), (6, 2, 1), (5, 4, 0), (5, 3, 1), (5, 2, 2), (4, 4, 1), (4, 3, 2), (3, 3, 3).
Автор задачи: Александр Ипатов
Источник задачи: Открытое личное первенство УрФУ по программированию 2012