import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler458 {

    static final long MOD = 1000000000L;
    static final int kLen = 6;
    static final int kAlphabet = 7;

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

    static class Pattern {
        byte[] p = new byte[kLen];

        Pattern() {
        }

        Pattern(byte[] p) {
            System.arraycopy(p, 0, this.p, 0, kLen);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(p);
        }

        @Override
        public boolean equals(Object obj) {
            return Arrays.equals(p, ((Pattern) obj).p);
        }
    }

    static Pattern canonicalize(Pattern p) {
        int[] remap = new int[kAlphabet + 1];
        Arrays.fill(remap, -1);
        int next = 0;
        Pattern out = new Pattern();
        for (int i = 0; i < kLen; i++) {
            int v = p.p[i];
            if (remap[v] == -1) {
                remap[v] = next++;
            }
            out.p[i] = (byte) remap[v];
        }
        return out;
    }

    static void generatePatterns(int pos, int currentMax, Pattern current, List<Pattern> out) {
        if (pos == kLen) {
            out.add(new Pattern(current.p));
            return;
        }
        for (int v = 0; v <= currentMax + 1; v++) {
            current.p[pos] = (byte) v;
            generatePatterns(pos + 1, Math.max(v, currentMax), current, out);
        }
    }

    static long[][] multiplyMatrix(long[][] a, long[][] b) {
        int n = a.length;
        long[][] c = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long sum = 0;
                for (int k = 0; k < n; k++) {
                    sum = (sum + a[i][k] * b[k][j]) % MOD;
                }
                c[i][j] = sum;
            }
        }
        return c;
    }

    static long[] multiplyMatVec(long[][] a, long[] v) {
        int n = a.length;
        long[] out = new long[n];
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < n; j++) {
                sum = (sum + a[i][j] * v[j]) % MOD;
            }
            out[i] = sum;
        }
        return out;
    }

    public static String solve() {
        long n = 1000000000000L;
        if (n == 0)
            return "1";
        if (n <= 6)
            return Long.toString(modPow(7, n));

        List<Pattern> patterns = new ArrayList<>();
        Pattern seed = new Pattern();
        generatePatterns(1, 0, seed, patterns);

        Map<Pattern, Integer> idByKey = new HashMap<>();
        for (int i = 0; i < patterns.size(); i++) {
            idByKey.put(patterns.get(i), i);
        }

        int stateCount = patterns.size();
        long[][] trans = new long[stateCount][stateCount];

        for (int i = 0; i < stateCount; i++) {
            Pattern p = patterns.get(i);
            int k = 0;
            for (byte b : p.p) {
                k = Math.max(k, b + 1);
            }

            for (int label = 0; label < k; label++) {
                Pattern next = new Pattern();
                for (int t = 0; t < kLen - 1; t++) {
                    next.p[t] = p.p[t + 1];
                }
                next.p[kLen - 1] = (byte) label;
                next = canonicalize(next);
                int nid = idByKey.get(next);
                trans[nid][i] = (trans[nid][i] + 1) % MOD;
            }

            int newCount = kAlphabet - k;
            if (newCount > 0 && k < 6) {
                Pattern next = new Pattern();
                for (int t = 0; t < kLen - 1; t++) {
                    next.p[t] = p.p[t + 1];
                }
                next.p[kLen - 1] = (byte) k;
                next = canonicalize(next);
                int nid = idByKey.get(next);
                trans[nid][i] = (trans[nid][i] + newCount) % MOD;
            }
        }

        long[] vec = new long[stateCount];
        for (int i = 0; i < stateCount; i++) {
            Pattern p = patterns.get(i);
            int k = 0;
            for (byte b : p.p) {
                k = Math.max(k, b + 1);
            }
            long ways = 1;
            for (int t = 0; t < k; t++) {
                ways = (ways * (kAlphabet - t)) % MOD;
            }
            vec[i] = ways;
        }

        long steps = n - 6;
        long[][] power = trans;

        while (steps > 0) {
            if ((steps & 1) != 0) {
                vec = multiplyMatVec(power, vec);
            }
            steps >>= 1;
            if (steps > 0) {
                power = multiplyMatrix(power, power);
            }
        }

        long answer = 0;
        for (long v : vec) {
            answer = (answer + v) % MOD;
        }

        return Long.toString(answer);
    }

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