Staircase Painting

There is a staircase with \(3^N\) steps. HG paints each step according to the following rule: for the \(I\)-th step from the top, if \(V_3(I)\) is odd then the left side is painted, otherwise the right side is painted. Here \(V_3(I)\) is defined as the exponent of \(3\) in the prime factorization of \(I\) (i.e. the number of times \(3\) divides \(I\)).

Little Y, who has an extreme obsession with cleanliness, does not want to step on any paint. He will walk down the staircase one step at a time. At each step he must alternate his foot: if he stands on the left side on the current step then he must stand on the right side of the next step, and vice versa. Moreover, if a step is painted on the left side, he has to stand on the right side to avoid the paint, and vice versa.

Little Y can only choose on which side he stands on the first step. Hence, he has exactly 2 possible ways to go down the staircase. Let these two choices correspond to binary strings:

• A = 101010…101, meaning he stands on left at step 1, right at step 2, and so on.
• B = 010101…010, meaning he stands on right at step 1, left at step 2, and so on.

The painting on each step is described by another binary string C of length \(3^N\) where the \(I\)-th character is \(V_3(I) \bmod 2\) (note that if \(V_3(I)\) is odd, then the left side is painted (represented by 1), otherwise the right side is painted (represented by 0)).

Define \(\operatorname{mc}(X,Y)\) as the number of positions where the two binary strings \(X\) and \(Y\) have matching characters. In our setting, matching means that Little Y would be stepping on the painted part. His aim is to minimize the number of times he steps on paint. Formally, we wish to compute:

[ \min{\operatorname{mc}(A,C),; \operatorname{mc}(B,C)} \mod (10^9+7). ]

Observation: For each step \(1 \le i \le 3^N\), note that the strings A and B are complementary. In fact, for any index \(i\), exactly one of A or B matches C. Hence if we let \(f(N)=\operatorname{mc}(A,C)\), then \(\operatorname{mc}(B,C)=3^N-f(N)\) and the required answer is

[ \min{f(N),3^N-f(N)}. ]

A detailed analysis shows that the answer can be simplified to

[ \frac{3^N-1}{2} \mod (10^9+7). ]

Your task is to compute \(\frac{3^N-1}{2}\) modulo \(10^9+7\) given the integer \(N\).

inputFormat

The input contains a single integer \(N\) (\(0 \le N \le 10^9\) or as specified by the problem constraints).

outputFormat

Output one integer, the value of \(\frac{3^N-1}{2}\) modulo \(10^9+7\).

sample

0

0