Problem Description

The top of an ancient city wall in country $X$ can be seen as a rectangle made up of $2 \times N$ cells (as shown in Figure $1$). Now these cells need to be painted with protective paint.

You may start painting from any cell. After finishing one cell, you can move to a cell adjacent to it (diagonal adjacency also counts), but you cannot move to a farther cell (because the paint has not dried and you cannot step on it).

For example, adbcef is a valid painting order.

cefdab is another valid plan.

Given $N$, find the total number of valid plans. When $N$ is large, the result will grow rapidly, so output the result modulo $1000000007(10^9+7)$.

Input Format

The input is a positive integer $N$ (not greater than $1000$).

Output Format

Output a positive integer.

2

24

3

96

22

359635897

Hint

Time limit: 1 second, 64 MB. Lanqiao Cup 2013, the 4th National Contest.

Translated by ChatGPT 5