You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

* The string does not contain characters other than `A`, `C`, `G` and `T`.
* The string does not contain `AGC` as a substring.
* The condition above cannot be violated by swapping two adjacent characters once.

Constraints

* 3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:


N


Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Examples

Input

3


Output

61


Input

4


Output

230


Input

100


Output

388130742
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static final int MODULUS = 1_000_000_007;
    static final char[] ALPHABET = { 'A', 'C', 'G', 'T' };
    static final Set<String> EXCLUDED_PATTERNS = new HashSet<>(
            Arrays.asList("AGC", "GAC", "ACG", "AGGC", "ATGC", "AGTC"));

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        System.out.println(solve(N));

        sc.close();
    }

    static int solve(int N) {
        Map<String, Integer> patternToWayNum = new HashMap<>();
        patternToWayNum.put("", 1);

        for (int i = 0; i < N; ++i) {
            Map<String, Integer> nextPatternToWayNum = new HashMap<>();
            for (String pattern : patternToWayNum.keySet()) {
                for (char letter : ALPHABET) {
                    String nextPattern = pattern + letter;
                    if (nextPattern.length() > 4) {
                        nextPattern = nextPattern.substring(nextPattern.length() - 4);
                    }
                    String nextLastThreePattern = (nextPattern.length() == 4) ? nextPattern.substring(1) : nextPattern;

                    if (!EXCLUDED_PATTERNS.contains(nextPattern) && !EXCLUDED_PATTERNS.contains(nextLastThreePattern)) {
                        nextPatternToWayNum.put(nextPattern,
                                addMod(nextPatternToWayNum.getOrDefault(nextPattern, 0), patternToWayNum.get(pattern)));
                    }
                }
            }

            patternToWayNum = nextPatternToWayNum;
        }

        return patternToWayNum.values().stream().mapToInt(x -> x).reduce(Main::addMod).getAsInt();
    }

    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }
}