public class Euler422 {
    private static final long MOD = 1000000007L;
    private static final long MOD_EXP = MOD - 1L;

    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        long cur = (base % mod + mod) % mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            exp >>= 1;
        }
        return result;
    }

    private static long modInv(long x) {
        return modPow(x, MOD - 2, MOD);
    }

    private static class Pair {
        long a, b;

        Pair(long a, long b) {
            this.a = a;
            this.b = b;
        }
    }

    private static Pair fibPairMod(long n, long mod) {
        if (n == 0)
            return new Pair(0, 1 % mod);
        Pair p = fibPairMod(n >> 1, mod);
        long a = p.a, b = p.b;

        long twoBMinusA = (2 * b - a) % mod;
        if (twoBMinusA < 0)
            twoBMinusA += mod;

        long c = (a * twoBMinusA) % mod;
        long d = ((a * a) % mod + (b * b) % mod) % mod;

        if ((n & 1) != 0) {
            return new Pair(d, (c + d) % mod);
        }
        return new Pair(c, d);
    }

    public static String solve() {
        long n = 1;
        for (int i = 0; i < 14; i++)
            n *= 11;

        long k = n - 1;
        Pair p = fibPairMod(k, MOD_EXP);
        long F = p.a;
        long L = (2 * p.b - p.a) % MOD_EXP;
        if (L < 0)
            L += MOD_EXP;

        int sign = (k % 3 == 0) ? 1 : -1;

        long twoPowL = modPow(2, L, MOD);
        long threePowF = modPow(3, F, MOD);

        long alpha, beta;
        long g1, g2;

        if ((n & 1) != 0) {
            alpha = twoPowL;
            beta = threePowF;
            g1 = (n == 1) ? 4 : 12;
            g2 = 1;
        } else {
            alpha = threePowF;
            beta = twoPowL;
            g1 = 1;
            g2 = (n == 2) ? 6 : 12;
        }

        long alpha2 = (alpha * alpha) % MOD;
        long beta2 = (beta * beta) % MOD;

        long n1 = (3 * alpha2 + 4 * beta2) % MOD;
        long n2 = (4 * alpha2 - 3 * beta2) % MOD;
        if (n2 < 0)
            n2 += MOD;

        long dBase = (twoPowL * threePowF) % MOD;

        long a = (n1 * modInv(g1)) % MOD;
        long b = (dBase * modInv(g1)) % MOD;
        long c = (n2 * modInv(g2)) % MOD;
        long d = (dBase * modInv(g2)) % MOD;

        if (sign < 0) {
            a = (MOD - a) % MOD;
            c = (MOD - c) % MOD;
        }

        long ans = (a + b + c + d) % MOD;
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}