public class Euler910 {
    static final int DEG = 40;
    static final long MOD = 1000000000L;

    static class Poly {
        long[] c = new long[DEG];

        long eval(long x) {
            long res = 0;
            long p = 1;
            for (int i = 0; i < DEG; ++i) {
                res = (res + p * c[i]) % MOD;
                p = (p * x) % MOD;
            }
            return res;
        }
    }

    static Poly exponentPoly = new Poly();

    static Poly addPoly(Poly a, Poly b) {
        Poly res = new Poly();
        for (int i = 0; i < DEG; ++i) {
            res.c[i] = (a.c[i] + b.c[i]) % MOD;
        }
        return res;
    }

    static Poly lambdaPoly(Poly a, long k) {
        Poly res = new Poly();
        for (int i = 0; i < DEG; ++i) {
            res.c[i] = (a.c[i] * k) % MOD;
        }
        return res;
    }

    static Poly shiftPoly(Poly p) {
        Poly res = new Poly();
        long last = p.c[DEG - 1];
        for (int i = DEG - 1; i > 0; --i) {
            res.c[i] = p.c[i - 1];
        }
        res.c[0] = 0;
        return addPoly(res, lambdaPoly(exponentPoly, last));
    }

    static Poly mulPoly(Poly p, Poly q) {
        Poly res = new Poly();
        Poly curQ = new Poly();
        System.arraycopy(q.c, 0, curQ.c, 0, DEG);
        for (int i = 0; i < DEG; ++i) {
            res = addPoly(res, lambdaPoly(curQ, p.c[i]));
            curQ = shiftPoly(curQ);
        }
        return res;
    }

    static Poly powPoly(Poly p, long n) {
        Poly res = new Poly();
        res.c[0] = 1;
        Poly curP = new Poly();
        System.arraycopy(p.c, 0, curP.c, 0, DEG);
        while (n > 0) {
            if ((n & 1) != 0) {
                res = mulPoly(res, curP);
            }
            n >>= 1;
            if (n > 0) {
                curP = mulPoly(curP, curP);
            }
        }
        return res;
    }

    static Poly composePoly(Poly p, Poly q) {
        Poly res = new Poly();
        Poly prod = new Poly();
        prod.c[0] = 1;
        for (int i = 0; i < DEG; ++i) {
            res = addPoly(res, lambdaPoly(prod, p.c[i]));
            prod = mulPoly(prod, q);
        }
        return res;
    }

    static Poly iterCompose(Poly p, long n) {
        if (n == 0) {
            Poly id = new Poly();
            id.c[0] = 1;
            return id;
        }

        Poly res = new Poly();
        boolean init = false;
        Poly curP = new Poly();
        System.arraycopy(p.c, 0, curP.c, 0, DEG);
        while (n > 0) {
            if ((n & 1) != 0) {
                if (!init) {
                    System.arraycopy(curP.c, 0, res.c, 0, DEG);
                    init = true;
                } else {
                    res = composePoly(curP, res);
                }
            }
            n >>= 1;
            if (n > 0) {
                curP = composePoly(curP, curP);
            }
        }
        return res;
    }

    static Poly d1(long n) {
        Poly p = new Poly();
        p.c[1] = 1;
        Poly q = powPoly(p, n);
        return addPoly(q, shiftPoly(q));
    }

    static Poly d2(long n, Poly u) {
        Poly w = iterCompose(u, n);
        return composePoly(w, shiftPoly(u));
    }

    static Poly d3(long n, long m, long l) {
        if (n == 0) {
            Poly u = d1(l);
            Poly v = d2(m, u);
            return composePoly(u, v);
        }
        Poly u = d3(n - 1, m, l);
        return d2(m, u);
    }

    static void initExponentPoly() {
        exponentPoly = new Poly();
        exponentPoly.c[0] = 1;

        for (long i = 1; i <= DEG; ++i) {
            for (int j = DEG - 1; j > 0; --j) {
                exponentPoly.c[j] = (exponentPoly.c[j - 1] + i * exponentPoly.c[j]) % MOD;
            }
            exponentPoly.c[0] = (exponentPoly.c[0] * i) % MOD;
        }

        for (int i = 0; i < DEG; ++i) {
            exponentPoly.c[i] = (MOD - exponentPoly.c[i]) % MOD;
        }
    }

    public static String solve() {
        long a = 12;
        long b = 345678;
        long c = 9012345;
        long d = 678;
        long e = 90;

        initExponentPoly();
        Poly pPoly = d3(a, b, c);
        long ans = (pPoly.eval(d) + e) % MOD;
        return String.format("%09d", ans);
    }

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