Painting the Ancient City Wall

The ancient wall in country X can be considered as a 2×N grid (see Figure 1). It is required to paint all of the 2×N cells with protective paint. You may start from any cell. After painting a cell, you can move to any cell adjacent to it. Two cells are considered adjacent if they share a side or a corner (that is, the move may be vertical, horizontal, or diagonal). However, you cannot jump to a non‐adjacent cell (because the paint is still wet and you cannot step on it!).

For example, for a 2×3 grid (with 6 cells labeled with letters), the orders adbcef and cefdab are both valid painting orders.

Your task is: Given an integer \(N\), count the total number of valid painting sequences (i.e. Hamiltonian paths on the 2×N grid) modulo \(10^9+7\). That is, compute \(f(N) \bmod (10^9+7)\).

It can be proved that the number of valid orders satisfies the linear recurrence \[ f(1)=2,\quad f(2)=24,\quad f(n)=5\,f(n-1)-4\,f(n-2) \quad (n\ge3). \]

Note: The entire grid must be painted, and the order in which the cells are painted is a permutation of all 2×N cells such that every consecutive pair of cells in the sequence is adjacent (in one of the eight directions).

Figure 1: Illustration of a 2×N grid representing the top of an ancient wall.

inputFormat

The input consists of a single line containing an integer \(N\) (\(1 \le N \le 10^{9}\)).

outputFormat

Output a single integer: the number of valid painting sequences modulo \(10^9+7\).

sample

1

2