import java.math.BigInteger;

public class Euler885 {

    static long SMod(int n, long mod) {
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = fact[i - 1] * i;
        }

        long[] pow10Mod = new long[n + 1];
        long[] repMod = new long[n + 1];

        pow10Mod[0] = 1 % mod;
        repMod[0] = 0;

        for (int i = 1; i <= n; ++i) {
            pow10Mod[i] = (pow10Mod[i - 1] * 10L) % mod;
        }

        for (int i = 1; i <= n; ++i) {
            repMod[i] = (repMod[i - 1] * 10L + 1L) % mod;
        }

        long[] ans = { 0 };

        dfs(1, n, 0, 1L, 0L, n, fact, pow10Mod, repMod, mod, ans);

        return ans[0];
    }

    static void dfs(int digit, int rem, int s, long denom, long valMod, int n, long[] fact, long[] pow10Mod,
            long[] repMod, long mod, long[] ans) {
        if (digit == 10) {
            long ways = fact[n] / (fact[n - s] * denom);
            ans[0] = (ans[0] + (ways % mod) * valMod) % mod;
            return;
        }

        for (int c = 0; c <= rem; ++c) {
            long nextDenom = denom * fact[c];
            long nextMod = (valMod * pow10Mod[c] + ((long) digit * repMod[c]) % mod) % mod;
            dfs(digit + 1, rem - c, s + c, nextDenom, nextMod, n, fact, pow10Mod, repMod, mod, ans);
        }
    }

    public static String solve() {
        long MOD = 1123455689L;
        return Long.toString(SMod(18, MOD));
    }

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