public class Euler377 {
    private static final long kMod = 1000000000L;
    private static final int kSize = 18;

    private static long[][] zeroMatrix() {
        return new long[kSize][kSize];
    }

    private static long[][] multiply(long[][] a, long[][] b) {
        long[][] c = zeroMatrix();
        for (int i = 0; i < kSize; ++i) {
            for (int k = 0; k < kSize; ++k) {
                if (a[i][k] == 0)
                    continue;
                for (int j = 0; j < kSize; ++j) {
                    if (b[k][j] == 0)
                        continue;
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % kMod;
                }
            }
        }
        return c;
    }

    private static long[] applyMatrixVector(long[][] a, long[] v) {
        long[] out = new long[kSize];
        for (int i = 0; i < kSize; ++i) {
            long sum = 0;
            for (int j = 0; j < kSize; ++j) {
                if (a[i][j] == 0 || v[j] == 0)
                    continue;
                sum += a[i][j] * v[j];
            }
            out[i] = sum % kMod;
        }
        return out;
    }

    private static long[][] buildTransition() {
        long[][] t = zeroMatrix();
        for (int i = 0; i < 9; ++i) {
            t[0][i] = 1;
        }
        for (int i = 1; i < 9; ++i) {
            t[i][i - 1] = 1;
        }
        for (int i = 0; i < 9; ++i) {
            t[9][i] = i + 1;
            t[9][9 + i] = 10;
        }
        for (int i = 10; i < 18; ++i) {
            t[i][i - 1] = 1;
        }
        return t;
    }

    public static String solve() {
        long[][] transition = buildTransition();
        long[][][] powers = new long[64][][];
        powers[0] = transition;
        for (int i = 1; i < 64; ++i) {
            powers[i] = multiply(powers[i - 1], powers[i - 1]);
        }

        long ans = 0;
        long p13 = 1;
        for (int i = 1; i <= 17; ++i) {
            p13 *= 13L;

            long[] state = new long[kSize];
            state[0] = 1;
            long e = p13;
            int bit = 0;
            while (e > 0) {
                if ((e & 1L) != 0L) {
                    state = applyMatrixVector(powers[bit], state);
                }
                e >>= 1L;
                ++bit;
            }

            ans = (ans + state[9]) % kMod;
        }
        return String.valueOf(ans);
    }

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