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

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 10⁹ + 7 of the number of positions of the control sticks that Soren and Alba should check.