import java.math.BigInteger;

public class Euler506 {
    private static final long kMod = 123454321L;
    private static final BigInteger kBlockBase = BigInteger.valueOf(1000000L);
    private static final int[] kDigits = { 1, 2, 3, 4, 3, 2 };

    private static long modPow(long base, long exp, long mod) {
        long result = 1L % mod;
        long cur = base % mod;
        long e = exp;
        while (e > 0L) {
            if ((e & 1L) != 0L) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            e >>= 1L;
        }
        return result;
    }

    private static long[] extendedGcd(long a, long b) {
        if (b == 0)
            return new long[] { a, 1, 0 };
        long[] res = extendedGcd(b, a % b);
        long g = res[0];
        long x1 = res[1];
        long y1 = res[2];
        long x = y1;
        long y = x1 - (a / b) * y1;
        return new long[] { g, x, y };
    }

    private static long modInverse(long a, long mod) {
        long[] res = extendedGcd(a, mod);
        if (res[0] != 1)
            return 0L;
        long x = res[1] % mod;
        if (x < 0)
            x += mod;
        return x;
    }

    private static BigInteger[] directTermsExact(int count) {
        BigInteger[] out = new BigInteger[count + 1];
        int pos = 0;
        for (int n = 1; n <= count; ++n) {
            int s = 0;
            BigInteger val = BigInteger.ZERO;
            while (s < n) {
                int d = kDigits[pos];
                pos = (pos + 1) % 6;
                s += d;
                val = val.multiply(BigInteger.TEN).add(BigInteger.valueOf(d));
            }
            if (s != n)
                return new BigInteger[0];
            out[n] = val;
        }
        return out;
    }

    private static long geometricSum(long ratio, long terms, long mod, long invRatioMinusOne) {
        if (terms == 0)
            return 0L;
        long p = modPow(ratio, terms, mod);
        long numerator = (p + mod - 1L) % mod;
        return (numerator * invRatioMinusOne) % mod;
    }

    public static void main(String[] args) {
        long nMax = 100000000000000L;
        BigInteger[] terms = directTermsExact(45);
        if (terms.length == 0)
            return;

        long[] base = new long[15];
        long[] add = new long[15];

        for (int r = 1; r <= 15; ++r) {
            BigInteger v0 = terms[r];
            BigInteger v1 = terms[r + 15];
            BigInteger v2 = terms[r + 30];
            BigInteger c = v1.subtract(v0.multiply(kBlockBase));
            if (!v2.equals(v1.multiply(kBlockBase).add(c)))
                return;
            base[r - 1] = v0.longValue();
            add[r - 1] = c.longValue();
        }

        long invBMinus1 = modInverse(kBlockBase.longValue() - 1L, kMod);
        if (invBMinus1 == 0L)
            return;

        long total = 0L;
        for (int r = 1; r <= 15; ++r) {
            if (nMax < r)
                break;
            long count = (nMax - r) / 15L + 1L;
            long g = geometricSum(kBlockBase.longValue(), count, kMod, invBMinus1);
            long countMod = count % kMod;
            long gMinusCount = (g + kMod - countMod) % kMod;
            long t = (gMinusCount * invBMinus1) % kMod;

            long partBase = ((base[r - 1] % kMod) * g) % kMod;
            long partAdd = ((add[r - 1] % kMod) * t) % kMod;

            total = (total + partBase) % kMod;
            total = (total + partAdd) % kMod;
        }
        System.out.println(total);
    }
}