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

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

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

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

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