Painting blocks

Time limit2sMemory limit512 MB

Summary

Count colorings of N blocks with 4 colors so that the number of red and yellow blocks are both even, modulo 10007.

Level: Medium6 of 10
Topics: Combinatorics, Math, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

N blocks lie in a row. Minho paints each block with one of four colors: red, orange, yellow, green.

He wants to know how many paintings have both an even number of red blocks and an even number of yellow blocks. The positions are fixed, so two paintings that differ in the color of any single position count as different. A count of 0 is even.

Write a program that reads N and computes the number of such paintings.

Input

The first line contains N ( $1 \le N \le 10^9$ ).

Output

Print the number of paintings in which the number of red blocks and the number of yellow blocks are both divisible by 2, modulo 10007.

Examples4

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
6
```
Example 3
Input
```
3
```
Expected output
```
20
```
Example 4
Input
```
8
```
Expected output
```
6505
```