public class Euler741 {
    static final long kMod = 1000000007L;

    static long modPow(long base, long exp) {
        long res = 1L;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * base) % kMod;
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return res;
    }

    static long computeG(int n) {
        if (n <= 0)
            return 0;
        int invSize = Math.max(n + 2, 9);
        int[] inv = new int[invSize];
        inv[1] = 1;
        for (int i = 2; i < invSize; ++i) {
            inv[i] = (int) (kMod - (kMod / i) * inv[(int) (kMod % i)] % kMod);
        }
        long inv2 = inv[2];
        long inv3 = inv[3];
        long inv8 = inv[8];

        int m = n / 2;

        long fact = 1;
        long factM = 1;
        for (int i = 1; i <= n; ++i) {
            fact = (fact * i) % kMod;
            if (i == m)
                factM = fact;
        }
        long factN = fact;

        long aPrev = 1;
        long aCurr = 0;
        for (int i = 1; i < n; ++i) {
            long aNext = (i * aCurr + inv2 * aPrev) % kMod;
            aNext = (aNext * inv[i + 1]) % kMod;
            aPrev = aCurr;
            aCurr = aNext;
        }
        long aN = (n == 0) ? aPrev : aCurr;
        long f = factN * factN % kMod * aN % kMod;

        long bN = 0;
        if (n == 0) {
            bN = 1;
        } else if (n == 1) {
            bN = 0;
        } else if (n == 2) {
            bN = inv2;
        } else if (n == 3) {
            bN = (2 * inv3) % kMod;
        } else {
            long bNm3 = 1;
            long bNm2 = 0;
            long bNm1 = inv2;
            long bCurr = (2 * inv3) % kMod;
            for (int i = 3; i < n; ++i) {
                long bNext = (2L * i % kMod * bCurr % kMod
                        - (i - 2) * bNm1 % kMod
                        - inv2 * bNm3 % kMod) % kMod;
                if (bNext < 0)
                    bNext += kMod;
                bNext = (bNext * inv[i + 1]) % kMod;
                bNm3 = bNm2;
                bNm2 = bNm1;
                bNm1 = bCurr;
                bCurr = bNext;
            }
            bN = bCurr;
        }
        long D = factN * bN % kMod;

        long R2 = 0;
        if (m > 0) {
            long hPrev = 1;
            long hCurr = 1;
            long pCurr = 0;
            for (int k = 1; k <= m; ++k) {
                pCurr = (4 * pCurr + 2 * hPrev) % kMod;
                long hNext = ((4L * k + 1) % kMod * hCurr + 4 * hPrev) % kMod;
                hNext = (hNext * inv[k + 1]) % kMod;
                hPrev = hCurr;
                hCurr = hNext;
            }
            long hM = hPrev;
            long factMSq = factM * factM % kMod;
            if (n % 2 == 0) {
                R2 = factMSq * hM % kMod;
            } else {
                R2 = factMSq * pCurr % kMod;
            }
        }

        long R90 = 0;
        if (n % 2 == 0 && m > 0) {
            long cNm2 = 0;
            long cNm1 = 0;
            long cCurr = 1;
            for (int k = 0; k < m; ++k) {
                long cNext = ((2L * k + 1) % kMod * cCurr - cNm1 + 2 * cNm2) % kMod;
                if (cNext < 0)
                    cNext += kMod;
                cNext = (cNext * inv[k + 1]) % kMod;
                cNm2 = cNm1;
                cNm1 = cCurr;
                cCurr = cNext;
            }
            long cM = cCurr;
            R90 = factM * cM % kMod;
        }

        long V = 0;
        if (n % 2 == 0) {
            V = factN * modPow(inv2, n / 2) % kMod;
        }

        long g = (f + R2 + 2 * R90 + 2 * V + 2 * D) % kMod;
        g = g * inv8 % kMod;
        return g;
    }

    public static String solve() {
        int n1 = 1;
        for (int i = 0; i < 7; ++i)
            n1 *= 7;
        int n2 = 1;
        for (int i = 0; i < 8; ++i)
            n2 *= 8;

        long g1 = computeG(n1);
        long g2 = computeG(n2);
        long ans = (g1 + g2) % kMod;
        return Long.toString(ans);
    }

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