Coco wants to play the "King Game" using a $3 \times N$ chocolate bar and one chess king. The King Game (which is unrelated to the drinking game of the same name) is won by starting at the top-left cell of the chocolate bar, visiting every cell exactly once according to the movement rules of a chess king, and finally reaching the bottom-right cell. A king can move to any of the 8 adjacent cells from its current position, but it cannot move outside the chocolate bar.

Coco is curious about the number of ways to win the King Game. Help Coco solve this problem.

Input

The first line contains the integer $N$.

Output

Output the answer modulo $10^9$ on the first line.

Examples

Input 1

2

Output 1

6

Input 2

6

Output 2

11563

Note

$1 \le N \le 10^3$