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

1918. Titan Ruins: Artful Manipulations

Time limit: 2.0 second
Memory limit: 64 MB
`Listen, I think that the creators of this place were just mad about experimenting with coins,' said Soren entering another room. In this room, he saw a large platform with a lot of control sticks and a small coin lying on the platform. Just for fun, Alba sent a weak charge of magic energy to the platform. Suddenly, instead of one coin, several coins appeared at the same place, but soon they started to disappear one after another until only one coin remained. Alba sent one more charge, and several coins appeared again. Another charge, and the number of coins decreased.
Continuing the experiments, Soren and Alba discovered the following rules.
  • The number of coins on the platform after sending a magic charge depends only on the number of coins that were on the platform before the charge was sent and is independent of the charge size and other factors.
  • A charge may increase or decrease the number of coins, or the number of coins may stay the same. At any time there is at least one and at most n coins.
  • If no charge is sent for some time, the coins disappear one by one until one coins remains on the platform. This happens slowly, so that a new charge can be sent at any time—when there is any intermediate number of coins on the platform.
  • The platform has n control sticks, and each control stick can be in one of n positions. If, at some moment, there are i coins on the platform and the ith stick is in position j (1 ≤ jn), then the number of coins on the platform after a charge has been sent becomes j.
Having examined the platform thoroughly, Soren found a small hidden door. It was locked, and he conjectured that the door could be opened if the control sticks were in certain positions. Since there were too many combinations of positions, the friends decided to try only those combinations for which the maximum number of n coins could be obtained from one coin. There had to be a smaller number of such combinations, but how many?


You are given the integer n (2 ≤ n ≤ 5000).


Output the remainder in division by 109 + 7 of the number of positions of the control sticks that Soren and Alba should check.


Problem Author: Denis Dublennykh
Problem Source: NEERC 2012, Eastern subregional contest