public class Euler402 {
    private static final long MOD = 1000000000L;
    private static final int DIM = 11;

    private static long gcd(long x, long y) {
        while (y != 0) {
            long t = x % y;
            x = y;
            y = t;
        }
        return x < 0 ? -x : x;
    }

    private static long gcd4(long a, long b, long c, long d) {
        return gcd(gcd(a, b), gcd(c, d));
    }

    private static class Coefs {
        long a3 = 0;
        long[] a2 = new long[24];
        long[] a1 = new long[24];
        long[] a0 = new long[24];
    }

    private static Coefs buildCoefficients() {
        Coefs out = new Coefs();
        for (int ra = 1; ra <= 24; ++ra) {
            for (int rb = 1; rb <= 24; ++rb) {
                for (int rc = 1; rc <= 24; ++rc) {
                    long m = gcd4(24, 36 + 6L * ra, 14 + 6L * ra + 2L * rb, 1L + ra + rb + rc);
                    out.a3 = (out.a3 + m) % MOD;
                    for (int rem = 0; rem < 24; ++rem) {
                        int ea = (ra <= rem ? 1 : 0);
                        int eb = (rb <= rem ? 1 : 0);
                        int ec = (rc <= rem ? 1 : 0);
                        long u = m % MOD;
                        out.a2[rem] = (out.a2[rem] + u * (ea + eb + ec)) % MOD;
                        out.a1[rem] = (out.a1[rem] + u * (ea * eb + ea * ec + eb * ec)) % MOD;
                        out.a0[rem] = (out.a0[rem] + u * (ea * eb * ec)) % MOD;
                    }
                }
            }
        }
        return out;
    }

    private static class Mat {
        long[][] a = new long[DIM][DIM];
    }

    private static Mat matIdentity() {
        Mat m = new Mat();
        for (int i = 0; i < DIM; ++i) {
            m.a[i][i] = 1;
        }
        return m;
    }

    private static Mat matMul(Mat x, Mat y) {
        Mat z = new Mat();
        for (int i = 0; i < DIM; ++i) {
            for (int k = 0; k < DIM; ++k) {
                if (x.a[i][k] == 0)
                    continue;
                for (int j = 0; j < DIM; ++j) {
                    if (y.a[k][j] == 0)
                        continue;
                    z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
                }
            }
        }
        return z;
    }

    private static Mat matPow(Mat base, long exp) {
        Mat res = matIdentity();
        long e = exp;
        while (e > 0) {
            if ((e & 1) != 0) {
                res = matMul(base, res);
            }
            base = matMul(base, base);
            e >>= 1;
        }
        return res;
    }

    private static long[] matVecMul(Mat m, long[] v) {
        long[] out = new long[DIM];
        for (int i = 0; i < DIM; ++i) {
            long s = 0;
            for (int j = 0; j < DIM; ++j) {
                if (m.a[i][j] == 0)
                    continue;
                s = (s + m.a[i][j] * v[j]) % MOD;
            }
            out[i] = s;
        }
        return out;
    }

    private static Mat stepMatrix(int carry, int rem, Coefs coef) {
        Mat m = new Mat();
        long c = carry % MOD;
        long c2 = (c * c) % MOD;
        long c3 = (c2 * c) % MOD;

        m.a[0][0] = 1;
        m.a[1][2] = 1;
        m.a[2][0] = c;
        m.a[2][1] = 1;
        m.a[2][2] = 1;

        m.a[3][5] = 1;
        m.a[4][2] = c;
        m.a[4][4] = 1;
        m.a[4][5] = 1;

        m.a[5][0] = c2;
        m.a[5][1] = (2 * c) % MOD;
        m.a[5][2] = (2 * c) % MOD;
        m.a[5][3] = 1;
        m.a[5][4] = 2;
        m.a[5][5] = 1;

        m.a[6][9] = 1;
        m.a[7][5] = c;
        m.a[7][8] = 1;
        m.a[7][9] = 1;

        m.a[8][2] = c2;
        m.a[8][4] = (2 * c) % MOD;
        m.a[8][5] = (2 * c) % MOD;
        m.a[8][7] = 1;
        m.a[8][8] = 2;
        m.a[8][9] = 1;

        m.a[9][0] = c3;
        m.a[9][1] = (3 * c2) % MOD;
        m.a[9][2] = (3 * c2) % MOD;
        m.a[9][3] = (3 * c) % MOD;
        m.a[9][4] = (6 * c) % MOD;
        m.a[9][5] = (3 * c) % MOD;
        m.a[9][6] = 1;
        m.a[9][7] = 3;
        m.a[9][8] = 3;
        m.a[9][9] = 1;

        m.a[10][0] = coef.a0[rem];
        m.a[10][1] = coef.a1[rem];
        m.a[10][3] = coef.a2[rem];
        m.a[10][6] = coef.a3;
        m.a[10][10] = 1;

        return m;
    }

    public static String solve() {
        long kMax = 1234567890123L;
        Coefs coef = buildCoefficients();

        int[] fibMod24 = new int[24];
        fibMod24[0] = 0;
        fibMod24[1] = 1;
        for (int i = 2; i < 24; ++i) {
            fibMod24[i] = (fibMod24[i - 1] + fibMod24[i - 2]) % 24;
        }

        int[] carry = new int[24];
        for (int i = 0; i < 24; ++i) {
            carry[i] = (fibMod24[i] + fibMod24[(i + 1) % 24]) / 24;
        }

        Mat[] step = new Mat[24];
        for (int phase = 0; phase < 24; ++phase) {
            step[phase] = stepMatrix(carry[phase], fibMod24[phase], coef);
        }

        long steps = kMax - 1;
        int startPhase = 2 % 24;

        Mat block = matIdentity();
        for (int t = 0; t < 24; ++t) {
            int phase = (startPhase + t) % 24;
            block = matMul(step[phase], block);
        }

        long[] state = new long[DIM];
        state[0] = 1;

        long fullBlocks = steps / 24;
        int remSteps = (int) (steps % 24);

        if (fullBlocks > 0) {
            Mat blockPow = matPow(block, fullBlocks);
            state = matVecMul(blockPow, state);
        }

        for (int t = 0; t < remSteps; ++t) {
            int phase = (startPhase + t) % 24;
            state = matVecMul(step[phase], state);
        }

        return String.format("%09d", state[10] % MOD);
    }

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