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

Open Ural FU Personal Contest 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. 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.

Input

The only line contains an integer n (2 ≤ n ≤ 50).

Output

Output the number of possible forecasts about the look of the final chart modulo 109 + 7.

Sample

inputoutput
3
8

Notes

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
To submit the solution for this problem go to the Problem set: 1946. Chinese Hockey 3