public class Euler778 {

    static final long MOD = 1000000009L;
    static final int D = 10;

    static long[][] matMul(long[][] A, long[][] B) {
        long[][] C = new long[D][D];
        for (int i = 0; i < D; ++i) {
            for (int k = 0; k < D; ++k) {
                long aik = A[i][k];
                if (aik == 0)
                    continue;
                for (int j = 0; j < D; ++j) {
                    C[i][j] = (C[i][j] + aik * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    static long[][] matPow(long[][] base, long exp) {
        long[][] result = new long[D][D];
        for (int i = 0; i < D; ++i) {
            result[i][i] = 1;
        }

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = matMul(base, result);
            }
            base = matMul(base, base);
            exp >>= 1;
        }
        return result;
    }

    static long[] digitCounts(long M, long p10) {
        long N = M + 1;
        long block = 10L * p10;
        long full = N / block;
        long rem = N % block;

        long[] c = new long[D];
        for (int d = 0; d < D; ++d) {
            long cnt = full * p10;
            long shift = d * p10;
            if (rem > shift) {
                long extra = rem - shift;
                cnt += (extra < p10) ? extra : p10;
            }
            c[d] = cnt % MOD;
        }
        return c;
    }

    static long contributionForPosition(long R, long M, long p10) {
        long[] c = digitCounts(M, p10);

        long[][] T = new long[D][D];
        for (int from = 0; from < D; ++from) {
            for (int d = 0; d < D; ++d) {
                int to = (from * d) % 10;
                T[to][from] = (T[to][from] + c[d]) % MOD;
            }
        }

        long[][] P = matPow(T, R);

        long s = 0;
        for (int r = 0; r < D; ++r) {
            s = (s + r * P[r][1]) % MOD;
        }
        return s;
    }

    static long fMod(long R, long M) {
        long ans = 0;
        long placeMod = 1;

        for (long p10 = 1; p10 <= M; p10 *= 10L) {
            long s = contributionForPosition(R, M, p10);
            ans = (ans + placeMod * s) % MOD;
            placeMod = (placeMod * 10L) % MOD;
        }

        return ans;
    }

    public static String solve() {
        return Long.toString(fMod(234567, 765432));
    }

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