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.

输入格式

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. All examples have been verified by independent small-scale enumeration or state search.