Coloring a Grid — n × 3 with R/G/B

Color an n×3 grid with three colors: red, green, and blue. A valid coloring requires every row and every column to contain at least two colors. The source's sample outputs for n=3 and n=4 contradict the statement; following the statement, they are corrected to 9750 and 296490 respectively.

输入格式

A single integer n (site range 1≤n≤10^18).

输出格式

Output the number of valid colorings modulo 1,000,000,007.

样例 1

输入：

2

输出：

174

样例 2

输入：

3

输出：

9750

样例 3

输入：

4

输出：

296490

样例说明

Apply inclusion-exclusion to the events that each of the three columns is entirely one color; the answer is 24^n−9·8^n+9·2^n+18·3^n−24 (modulo).