|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||4||4||4||100.000%|
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).
In the last test case, the actual result is 8155103542731753 by we have to print it modulo 109 + 7.