시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB116807771.963%

## 문제

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.

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.

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 (109 + 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 109 + 7.