Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different.</p>

We can build rectangles of certain width W and height 3 using dominoes. We are wondering how many ways of creating such rectangles are possible.

Below you can see the three possible ways of creating a rectangle of width 2 and height 3.

As you see there are many ways of tiling the rectangle. For example this is a possible solution with width 12:

Your task is to write a program that computes the number of possible ways of tiling a rectangle of width W and height 3.

입력 형식

A single line with an integer W. The width of the rectangle.</p>

The value of W will be between 1 and 1000.

출력 형식

A single line with the number of possible ways. The numbers can be large so print the solution modulo 1000000007 (10⁹ + 7).

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

153

예제 입력 3

30

예제 출력 3

299303201

예제 입력 4

3

예제 출력 4

0

예제 입력 5

56

예제 출력 5

485646032

힌트

In the last test case, the actual result is 8155103542731753 by we have to print it modulo 10⁹ + 7.