public class Euler294 {
    static final int TARGET_SUM = 23;
    static final int MOD_23 = 23;

    static long[] polyMulMod(long[] a, long[] b, long mod) {
        long[] c = new long[TARGET_SUM + 1];
        for (int i = 0; i <= TARGET_SUM; ++i) {
            if (a[i] == 0)
                continue;
            for (int j = 0; i + j <= TARGET_SUM; ++j) {
                if (b[j] == 0)
                    continue;

                long term = (a[i] % mod) * (b[j] % mod);
                if (term < 0) { // Overflow prevention fallback
                    java.math.BigInteger bTerm = java.math.BigInteger.valueOf(a[i])
                            .multiply(java.math.BigInteger.valueOf(b[j]))
                            .mod(java.math.BigInteger.valueOf(mod));
                    c[i + j] = (c[i + j] + bTerm.longValue()) % mod;
                } else {
                    c[i + j] = (c[i + j] + term % mod) % mod;
                }
            }
        }
        return c;
    }

    static long[] polyPowDigitSum(long exponent, long mod) {
        long[] base = new long[TARGET_SUM + 1];
        for (int d = 0; d <= 9; ++d) {
            base[d] = 1;
        }

        long[] result = new long[TARGET_SUM + 1];
        result[0] = 1;

        long e = exponent;
        while (e > 0) {
            if ((e & 1) != 0) {
                result = polyMulMod(result, base, mod);
            }
            e >>= 1;
            if (e > 0) {
                base = polyMulMod(base, base, mod);
            }
        }

        return result;
    }

    static long countViaClassesMod(long n, long mod) {
        long q = n / 22L;
        int r = (int) (n % 22L);

        long[] cQ = polyPowDigitSum(q, mod);
        long[] cQ1 = polyPowDigitSum(q + 1L, mod);

        int[] weights = new int[22];
        int cur = 1;
        for (int i = 0; i < 22; ++i) {
            weights[i] = cur;
            cur = (cur * 10) % MOD_23;
        }

        long[][] dp = new long[TARGET_SUM + 1][MOD_23];
        dp[0][0] = 1;

        for (int cls = 0; cls < 22; ++cls) {
            long[] coeff = (cls < r) ? cQ1 : cQ;

            long[][] next = new long[TARGET_SUM + 1][MOD_23];

            for (int s = 0; s <= TARGET_SUM; ++s) {
                for (int rem = 0; rem < MOD_23; ++rem) {
                    long curCount = dp[s][rem];
                    if (curCount == 0)
                        continue;

                    for (int t = 0; s + t <= TARGET_SUM; ++t) {
                        long ways = coeff[t];
                        if (ways == 0)
                            continue;

                        int rem2 = (rem + weights[cls] * t) % MOD_23;

                        long term = (curCount % mod) * (ways % mod);
                        if (term < 0) {
                            java.math.BigInteger bTerm = java.math.BigInteger.valueOf(curCount)
                                    .multiply(java.math.BigInteger.valueOf(ways))
                                    .mod(java.math.BigInteger.valueOf(mod));
                            next[s + t][rem2] = (next[s + t][rem2] + bTerm.longValue()) % mod;
                        } else {
                            next[s + t][rem2] = (next[s + t][rem2] + term % mod) % mod;
                        }
                    }
                }
            }

            dp = next;
        }

        return dp[TARGET_SUM][0];
    }

    public static String solve() {
        return String.valueOf(countViaClassesMod(3138428376721L, 1000000000L));
    }

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