You are given an integer $N$. Find the number of strings of length $N$ that satisfy the following conditions, modulo $10^9+7$:

-   The string does not contain characters other than `A`, `C`, `G` and `T`.
-   The string does not contain `AGC` as a substring.

-   The condition above cannot be violated by swapping two adjacent characters once.

Notes
A substring of a string $T$ is a string obtained by removing zero or more characters from the beginning and the end of $T$.
For example, the substrings of `ATCODER` include `TCO`, `AT`, `CODER`, `ATCODER` and (the empty string), but not `AC`.

Input is given from Standard Input in the following format:

```
$N$
```

Print the number of strings of length $N$ that satisfy the following conditions, modulo $10^9+7$.

-   $3 \leq N \leq 100$

61

There are $4^3=64$ strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64−3=61.