ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1946. Chinese Hockey 3

Time limit: 1.0 second
Memory limit: 64 MB
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