The Major League of Table Hockey of China is an event, at
which n best players from all over the colonized Galaxy participate.
During the season every player of the League must play a single match
against every other player. The game continues until exactly 3 goals are
scored. Thus all matches end
either with a score of 3:0 or with a score 2:1 in favor of one of the
players. In the total chart of the League’s results the players are ranked
according to the total amount of the goals scored in all of their matches.
You are working for a betting office which takes predictions about the
look of the final chart. To win the competition one has to call the
exact number of the goals scored by the winner, the number of goals scored
by the close competitor and so on to the amount of goals scored by the
participant ranked last. One doesn’t have to name the players.
Help the agency to count the number of all possible predictions.
The only line contains an integer n (2 ≤ n ≤ 50).
Output the number of possible forecasts about the look of the final chart modulo 109 + 7.
The following forecasts are possible for three players: (6, 3, 0),
(6, 2, 1), (5, 4, 0), (5, 3, 1), (5, 2, 2), (4, 4, 1), (4, 3, 2),
(3, 3, 3).
Problem Author: Alexander Ipatov
Problem Source: Open Ural FU Personal Contest 2012