Coloring Houses

An even number n of houses stand in a row and are painted with three fixed colors. Any two adjacent houses, and any two houses at the same distance from the two ends, must have different colors. The same color in the catalog is an error. Output the answer modulo 10⁹+7. This catalog entry shares its source with an earlier problem; it keeps its own problem ID and is verified independently.

输入格式

One line with an even n in 2..100000.

输出格式

Output the single integer required by the problem.

样例 1

输入：

2

输出：

6

样例 2

输入：

4

输出：

18

样例 3

输入：

6

输出：

54

样例说明

The answers to the three public examples are, in order: 6; 18; 54. The examples were rechecked by independent enumeration, state search, or direct simulation.