public class Euler624 {
    static final long MOD = 1000000009L;

    static long modPow(long a, long e) {
        long r = 1 % MOD;
        a %= MOD;
        while (e > 0) {
            if ((e & 1) == 1)
                r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return r;
    }

    static class Mat2 {
        long a00, a01, a10, a11;

        Mat2(long a00, long a01, long a10, long a11) {
            this.a00 = a00;
            this.a01 = a01;
            this.a10 = a10;
            this.a11 = a11;
        }
    }

    static Mat2 matMul(Mat2 x, Mat2 y) {
        long r00 = (x.a00 * y.a00 % MOD + x.a01 * y.a10 % MOD) % MOD;
        long r01 = (x.a00 * y.a01 % MOD + x.a01 * y.a11 % MOD) % MOD;
        long r10 = (x.a10 * y.a00 % MOD + x.a11 * y.a10 % MOD) % MOD;
        long r11 = (x.a10 * y.a01 % MOD + x.a11 * y.a11 % MOD) % MOD;
        return new Mat2(r00, r01, r10, r11);
    }

    static Mat2 matPow(Mat2 base, long e) {
        Mat2 r = new Mat2(1, 0, 0, 1);
        Mat2 cur = base;
        while (e > 0) {
            if ((e & 1) == 1)
                r = matMul(r, cur);
            cur = matMul(cur, cur);
            e >>= 1;
        }
        return r;
    }

    static long pMod(long n) {
        long inv2 = (MOD + 1) / 2;
        Mat2 A = new Mat2(inv2, inv2, inv2, 0);

        Mat2 An = matPow(A, n);
        Mat2 An1 = matPow(A, n - 1);

        long w0 = An1.a00;
        long w1 = An1.a10;

        long m00 = (1 + MOD - An.a00) % MOD;
        long m01 = (0 + MOD - An.a01) % MOD;
        long m10 = (0 + MOD - An.a10) % MOD;
        long m11 = (1 + MOD - An.a11) % MOD;

        long det = (m00 * m11 % MOD + MOD - m01 * m10 % MOD) % MOD;
        long invDet = modPow(det, MOD - 2);

        long s1 = ((MOD - m10) % MOD * w0 % MOD + m00 * w1 % MOD) % MOD;
        return inv2 * (s1 * invDet % MOD) % MOD;
    }

    static long qP(long n) {
        long r = pMod(n);
        return (r == 0) ? MOD : r;
    }

    public static String solve() {
        return Long.toString(qP(1000000000000000000L));
    }

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