P8607 [Lanqiao Cup 2013 National B] Painting the Grid

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)$.

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

Output a positive integer.

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