Problem C
Deild Goðsagnanna

The members of the Competitive Programming Association of Iceland play League of Legends quite a lot. In League of Legends there are two teams, the blue team and the red team, each of which consists of five players. Each player picks one of the available champions to play for a match before it starts, and no two players can pick the same champion.

Each champion has its weaknesses and strengths, so it is important to pick the right champion that fits well with your teammates’ champions and against the opponents’ champions. Therefore it is crucial to pick champions wisely. In order to prevent the opponents from selecting specific champions, each team may ban several champions from being picked. Banning a champion means neither team may pick it.

The draft process has the following steps:

1. Blue team bans one champion.

2. Red team bans one champion.

3. Blue team bans one champion.

4. Red team bans one champion.

5. Blue team bans one champion.

6. Red team bans one champion.

7. Blue team picks one champion.

8. Red team picks two champions consecutively.

9. Blue team picks two champions consecutively.

10. Red team picks one champion.

11. Red team bans one champion.

12. Blue team bans one champion.

13. Red team bans one champion.

14. Blue team bans one champion.

15. Red team picks one champion.

16. Blue team picks two champions consecutively.

17. Red team picks one champion.

Originally there were only $20$ champions available, ¹ but the developers of the game keep adding more and more champions. We say two drafts differ if any of their steps differ. Currently, there are $n$ champions available to choose. How many different draft processes exist?

Note that it only matters in which step each champion is picked or banned.

Below you can see three images representing three draft processes where the teams picked their champions. The blue team is on the left and the red team is on the right. Banned champions appear from left to right. Picked champions appear from top to bottom.

Figure 1: Example of a draft process where champions where banned and picked.

In the above draft process, the following happens:

1. Blue team bans: Fizz.

2. Red team bans: Rumble.

3. Blue team bans: Skarner.

4. Red team bans: Ekko.

5. Blue team bans: Nami.

6. Red team bans: Olaf.

7. Blue team picks: Jarvan IV.

8. Red team picks: Kindred.

9. Red team picks: Lux.

10. Blue team picks: Brand.

11. Blue team picks: Tryndamere.

12. Red team picks: Rammus.

13. Red team bans: Twitch.

14. Blue team bans: Twisted Fate.

15. Red team bans: Malphite.

16. Blue team bans: Vladimir.

17. Red team picks: Jinx.

18. Blue team picks: Draven.

19. Blue team picks: Sett.

20. Red team picks: Blitzcrank.

Figure 2: This draft process is equivalent to the previous draft process.

In the above draft process, the same things happen as in the previous draft process, except that the blue team picks Tryndamere before picking Brand. Despite that, they are equivalent, since the two picks take place in the same step.

Figure 3: This draft process is different from the previous two draft processes.

In the above draft process, the same things happen as in the first draft process, except the red team picks Rammus before picking Lux. These picks take place in different steps, meaning this draft process differs from the previous two.

Input

Input consists of one line containing one integer $n$, the number of different available champions in the game.

Output

Suppose the number of different draft processes is the integer $k$. Note that $k$ can be a very large number. Therefore, you should output one line with one integer, the remainder after dividing $k$ by $1\, 000\, 000\, 007$.

Scoring

21

759105918

166

985420928