public class Euler356 {
    static long powMod(long base, long exp, long mod) {
        if (mod == 1)
            return 0;
        long res = 1;
        long cur = base % mod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * cur) % mod;
            cur = (cur * cur) % mod;
            exp >>= 1;
        }
        return res;
    }

    static long[][] multiplyMatrix(long[][] a, long[][] b, long mod) {
        long[][] out = new long[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                long s = 0;
                for (int k = 0; k < 3; k++) {
                    s += a[i][k] * b[k][j];
                }
                out[i][j] = s % mod;
            }
        }
        return out;
    }

    static long[][] powerMatrix(long[][] base, long exp, long mod) {
        long[][] res = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = multiplyMatrix(res, base, mod);
            base = multiplyMatrix(base, base, mod);
            exp >>= 1;
        }
        return res;
    }

    static long computeNewtonSumMod(int n, long exp, long mod) {
        long c = powMod(2, n, mod);
        long s0 = 3 % mod;
        long s1 = c;
        long s2 = (c * c) % mod;

        if (exp == 0)
            return s0;
        if (exp == 1)
            return s1;
        if (exp == 2)
            return s2;

        long[][] transition = {
                { c, 0, (mod - (n % mod)) % mod },
                { 1, 0, 0 },
                { 0, 1, 0 }
        };
        long[][] p = powerMatrix(transition, exp - 2, mod);
        long top = p[0][0] * s2 + p[0][1] * s1 + p[0][2] * s0;
        return top % mod;
    }

    public static String solve() {
        long mod = 100000000;
        long total = 0;
        for (int n = 1; n <= 30; n++) {
            long term = (computeNewtonSumMod(n, 987654321, mod) + mod - 1) % mod;
            total = (total + term) % mod;
        }
        return String.format("%08d", total);
    }

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