You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

<image>

An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109 + 7). 

Input

The first line contains the only integer n (1 ≤ n ≤ 107) — the required length of the cyclic path.

Output

Print the only integer — the required number of ways modulo 1000000007 (109 + 7).

Examples

Input

2


Output

3


Input

4


Output

21

Note

The required paths in the first sample are: 

  * D - A - D
  * D - B - D
  * D - C - D
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF113_Div2_E implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;
    
    final boolean ONLINE_JUDGE = (System.getProperty("ONLINE_JUDGE") != null);

    public static void main(String[] args) {
        new Thread(null, new CF113_Div2_E(), "", 256 * (1L << 20)).start();
    }

    @Override
    public void run() {
        try {
            long startTime = System.currentTimeMillis();
            if (ONLINE_JUDGE) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            Locale.setDefault(Locale.US);
            tok = new StringTokenizer("");
            solve();
            in.close();
            out.close();
            long endTime = System.currentTimeMillis();
            System.err.println("Time = " + (endTime - startTime));
            long freeMemory = Runtime.getRuntime().freeMemory();
            long totalMemory = Runtime.getRuntime().totalMemory();
            System.err.println("Memory = " + ((totalMemory - freeMemory) >> 10));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    /** http://pastebin.com/j0xdUjDn */
    static class Utils {

        private Utils() {}

        public static void mergeSort(int[] a) {
            mergeSort(a, 0, a.length - 1);
        }

        private static final int MAGIC_VALUE = 50;

        private static void mergeSort(int[] a, int leftIndex, int rightIndex) {
            if (leftIndex < rightIndex) {
                if (rightIndex - leftIndex <= MAGIC_VALUE) {
                    insertionSort(a, leftIndex, rightIndex);
                } else {
                    int middleIndex = (leftIndex + rightIndex) / 2;
                    mergeSort(a, leftIndex, middleIndex);
                    mergeSort(a, middleIndex + 1, rightIndex);
                    merge(a, leftIndex, middleIndex, rightIndex);
                }
            }
        }

        private static void merge(int[] a, int leftIndex, int middleIndex, int rightIndex) {
            int length1 = middleIndex - leftIndex + 1;
            int length2 = rightIndex - middleIndex;
            int[] leftArray = new int[length1];
            int[] rightArray = new int[length2];
            System.arraycopy(a, leftIndex, leftArray, 0, length1);
            System.arraycopy(a, middleIndex + 1, rightArray, 0, length2);
            for (int k = leftIndex, i = 0, j = 0; k <= rightIndex; k++) {
                if (i == length1) {
                    a[k] = rightArray[j++];
                } else if (j == length2) {
                    a[k] = leftArray[i++];
                } else {
                    a[k] = leftArray[i] <= rightArray[j] ? leftArray[i++] : rightArray[j++];
                }
            }
        }

        private static void insertionSort(int[] a, int leftIndex, int rightIndex) {
            for (int i = leftIndex + 1; i <= rightIndex; i++) {
                int current = a[i];
                int j = i - 1;
                while (j >= leftIndex && a[j] > current) {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = current;
            }
        }

    }
    
    void debug(Object... o) {
        if (!ONLINE_JUDGE) {
            System.err.println(Arrays.deepToString(o));
        }
    }

    // solution
    
    final int MOD = 1000*1000*1000 + 7;

    void solve() throws IOException {
        int n = readInt();
        int[][] dp = new int[4][n+1];
        dp[3][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    if (k != j) {
                        dp[j][i] = (dp[j][i] + dp[k][i-1]) % MOD;
                    }
                }
            }
        }
        out.print(dp[3][n]);
    }

}
