public class Euler672 {

    static final long MOD = 1117117717L;
    static final int DIM = 5;

    static long[][] identity() {
        long[][] m = new long[DIM][DIM];
        for (int i = 0; i < DIM; ++i) {
            m[i][i] = 1L;
        }
        return m;
    }

    static long[][] multiply(long[][] x, long[][] y) {
        long[][] z = new long[DIM][DIM];
        for (int i = 0; i < DIM; ++i) {
            for (int k = 0; k < DIM; ++k) {
                long xik = x[i][k];
                if (xik == 0L)
                    continue;
                for (int j = 0; j < DIM; ++j) {
                    long ykj = y[k][j];
                    if (ykj == 0L)
                        continue;
                    z[i][j] = (z[i][j] + xik * ykj) % MOD;
                }
            }
        }
        return z;
    }

    static long[][] power(long[][] base, long exp) {
        long[][] result = identity();
        while (exp > 0L) {
            if ((exp & 1L) != 0L) {
                result = multiply(base, result);
            }
            exp >>= 1L;
            if (exp > 0L) {
                base = multiply(base, base);
            }
        }
        return result;
    }

    static long[] applyMatrix(long[][] m, long[] v) {
        long[] out = new long[DIM];
        for (int i = 0; i < DIM; ++i) {
            long s = 0L;
            for (int j = 0; j < DIM; ++j) {
                s = (s + m[i][j] * v[j]) % MOD;
            }
            out[i] = s;
        }
        return out;
    }

    static long[][] digitMatrix(int d, int[] weight, int[] pref) {
        long[][] m = new long[DIM][DIM];
        m[0][0] = 1L;
        m[1][0] = 6L;
        m[1][1] = 7L;
        m[1][4] = d;
        m[2][0] = 15L;
        m[2][1] = 21L;
        m[2][2] = 7L;
        m[2][3] = d;
        m[2][4] = pref[d];
        m[3][3] = 1L;
        m[3][4] = weight[d];
        m[4][4] = 1L;
        return m;
    }

    static long[][] sequenceMatrix(String seq, int[] weight, int[] pref) {
        long[][] all = identity();
        for (int i = 0; i < seq.length(); ++i) {
            int d = seq.charAt(i) - '0';
            long[][] md = digitMatrix(d, weight, pref);
            all = multiply(md, all);
        }
        return all;
    }

    static long solveH(long k) {
        int[] weight = { 6, 5, 4, 3, 2, 1, 0 };
        int[] pref = new int[7];
        int run = 0;
        for (int d = 0; d < 7; ++d) {
            pref[d] = run;
            run += weight[d];
        }

        String blockA = "4311623550";
        String blockB = "431162355";
        String remSingle = "31162355";
        String remFirst = "311623550";

        long[][] MA = sequenceMatrix(blockA, weight, pref);
        long[][] MB = sequenceMatrix(blockB, weight, pref);
        long[][] MSingle = sequenceMatrix(remSingle, weight, pref);
        long[][] MFirst = sequenceMatrix(remFirst, weight, pref);

        long t = k / 10L;

        long[] v = { 1L, 3L, 12L, 2L, 1L };

        if (t == 1L) {
            v = applyMatrix(MSingle, v);
        } else {
            v = applyMatrix(MFirst, v);
            if (t > 2L) {
                long[][] mid = power(MA, t - 2L);
                v = applyMatrix(mid, v);
            }
            v = applyMatrix(MB, v);
        }

        return v[2] % MOD;
    }

    public static String solve() {
        long ans = solveH(1000000000L);
        return Long.toString(ans);
    }

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