CF584B.Kolya and Tanya

Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3_n_ gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3_n_ - 1, let the gnome sitting on the i-th place have a__i coins. If there is an integer i (0 ≤ i < n) such that a__i + a__i + n + a__i + 2_n_ ≠ 6, then Tanya is satisfied.

Count the number of ways to choose a__i so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 109 + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3_n_), such that a__i ≠ b__i (that is, some gnome got different number of coins in these two ways).

科里亚喜欢将小矮人围坐在圆桌旁并给他们分发硬币，而塔尼娅则喜欢研究坐在等边三角形三个顶点上的小矮人三元组。

更准确地说，共有 $3n$ 个小矮人围坐成一圈。每个小矮人可以拥有 $1$ 到 $3$ 枚硬币。我们将圆桌上各位置按顺时针（或逆时针）顺序编号为 $0$ 到 $3n-1$，设坐在第 $i$ 个位置上的小矮人拥有 $a_i$ 枚硬币。若存在某个整数 $i$（满足 $0 \le i < n$），使得

$$a_i + a_{i+n} + a_{i+2n} \ne 6,$$

则塔尼娅感到满意。

请计算满足塔尼娅满意条件的硬币分配方案总数。由于方案总数可能非常大，请输出该数对 $10^9 + 7$ 取模的结果。若存在某个下标 $i$（满足 $0 \le i < 3n$）使得 $a_i \ne b_i$，则称两种方案 $a$ 和 $b$ 是不同的（即至少有一个小矮人在两种方案中获得的硬币数量不同）。

A single line contains number n (1 ≤ n ≤ 105) — the number of the gnomes divided by three.

一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——即侏儒总数除以 3 的结果。

Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 109 + 7.

输出一个整数——满足塔尼娅条件的硬币分配方案数对 $10^9 + 7$ 取模后的余数。

20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex):

当 $ n = 1 $ 时，共有 20 种方式（编号为 0 的地精坐在三角形顶点，编号为 1 的地精坐在右顶点，编号为 2 的地精坐在左顶点）：