Problem C
Deild Goðsagnanna
Languages
en
is
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:

Blue team bans one champion.

Red team bans one champion.

Blue team bans one champion.

Red team bans one champion.

Blue team bans one champion.

Red team bans one champion.

Blue team picks one champion.

Red team picks two champions consecutively.

Blue team picks two champions consecutively.

Red team picks one champion.

Red team bans one champion.

Blue team bans one champion.

Red team bans one champion.

Blue team bans one champion.

Red team picks one champion.

Blue team picks two champions consecutively.

Red team picks one champion.
Originally there were only $20$ champions available, ^{1} 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.
In the above draft process, the following happens:

Blue team bans: Fizz.

Red team bans: Rumble.

Blue team bans: Skarner.

Red team bans: Ekko.

Blue team bans: Nami.

Red team bans: Olaf.

Blue team picks: Jarvan IV.

Red team picks: Kindred.

Red team picks: Lux.

Blue team picks: Brand.

Blue team picks: Tryndamere.

Red team picks: Rammus.

Red team bans: Twitch.

Blue team bans: Twisted Fate.

Red team bans: Malphite.

Blue team bans: Vladimir.

Red team picks: Jinx.

Blue team picks: Draven.

Blue team picks: Sett.

Red team picks: Blitzcrank.
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.
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
Group 
Points 
Constraints 
1 
30 
$20 \leq n \leq 21$ 
2 
25 
$20 \leq n \leq 100$ 
3 
20 
$20 \leq n \leq 10^{6}$ 
4 
15 
$20 \leq n \leq 10^{9}$ 
5 
10 
$20 \leq n \leq 10^{18}$ 
Sample Input 1  Sample Output 1 

21 
759105918 
Sample Input 2  Sample Output 2 

166 
985420928 
Footnotes
 In reality, there were $17$ champions originally, but the draft process required only $16$ champions back then.