Problem Description

A section of the ancient city wall in Country X can be seen as a rectangle composed of $2 \times N$ grids (as shown in Figure 1). Now, these grids need to be painted with protective paint.

You can start painting from any grid, and after painting one grid, you can move to an adjacent grid (including diagonal adjacency), but you cannot move to a farther grid (because the paint is not dry and cannot be stepped on!).

For example, adbcef is a valid painting sequence.

cefdab is another suitable scheme.

Given $N$, calculate the total number of schemes. When $N$ is large, the result grows rapidly, so please take the result modulo $1000000007 (10^9+7)$.

Input Format

The input data consists of a single positive integer $N$ (not exceeding $1000$).

Output Format

The output data consists of a single positive integer.

Sample Input and Output

Sample Input #1

2

Sample Output #1

24

Sample Input #2

3

Sample Output #2

96

Sample Input #3

22

Sample Output #3

359635897

Notes

Time limit: 1 second, Memory limit: 64MB. This problem is from the 4th LanQiao Cup National Finals in 2013.

见题面 Input 部分

见题面 Output 部分