Gahui and Club Audition 3

Time limit1sMemory limit512 MB

Summary

Count the patterns of a level lv key note under random reverse mode, where at most 6 reverse keys appear, modulo 1e9+7.

Level: Medium4 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Gahui is playing the 8-key normal mode of Club Audition. This mode has several key notes. A key note of level $lv$ contains $lv$ arrow keys. The player can choose 7 modes: reverse key modes 1 through 6, and random.

The kinds of arrow keys that appear depend on the level of the key note.

If $lv$ is 5 or less:
- Only the 4 arrow keys up, down, left, and right appear.
If $lv$ is 6 or more:
- The 8 forward keys up, down, left, right, up-right, down-right, up-left, and down-left can appear.
- Reverse keys of these 8 forward keys can also appear.
- When the reverse key mode is $c$ , the key note contains $c$ reverse keys. If the reverse key mode is random, the key note contains at most 6 reverse keys.

When Gahui chooses the random reverse key mode, print the number of patterns for a key note of level $lv$ , modulo $10^{9} + 7$ .

Input

The first line contains the level $lv$ of the key note.

Output

Print the answer to the problem.

Constraints

$1 \le lv \le 50\,000$

Examples2

Example 1
Input
```
6
```
Expected output
```
16777216
```
Example 2
Input
```
43985
```
Expected output
```
979440029
```