import java.util.stream.IntStream;

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

    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        if (base < 0)
            base += MOD;
        while (exp > 0) {
            if (exp % 2 == 1)
                res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    static long modInverse(long n) {
        return power(n, MOD - 2);
    }

    static long[] fact;
    static long[] invFact;
    static long[] powN;
    static long[] powN1;

    static void precompute(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        powN = new long[n + 1];
        powN1 = new long[n + 1];

        fact[0] = 1;
        powN[0] = 1;
        powN1[0] = 1;

        long nMod = n % MOD;
        long n1Mod = (MOD - (n - 1) % MOD) % MOD;

        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            powN[i] = (powN[i - 1] * nMod) % MOD;
            powN1[i] = (powN1[i - 1] * n1Mod) % MOD;
        }

        invFact[n] = modInverse(fact[n]);
        for (int i = n - 1; i >= 0; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    static long nCr(int n, int r) {
        if (r < 0 || r > n)
            return 0;
        return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
    }

    static long getC(int M, int k, int n) {
        if (M < 0)
            return 0;
        long sum = 0;
        int maxP = M / (k + 1);

        for (int p = 0; p <= maxP; p++) {
            long term = nCr(M - p * k, p);
            term = (term * powN[M - p * (k + 1)]) % MOD;
            term = (term * powN1[p]) % MOD;
            sum = (sum + term) % MOD;
        }
        return sum;
    }

    static long solveF(int n) {
        precompute(n);

        long totalSequences = power(n, n + 1);

        long sumNk = IntStream.range(1, n)
                .parallel()
                .mapToLong(k -> {
                    long cN1 = getC(n - 1, k, n);
                    long cN1k = getC(n - 1 - k, k, n);

                    long Wn = ((long) n * cN1) % MOD;
                    long sub = ((long) n * cN1k) % MOD;

                    Wn = (Wn - sub + MOD) % MOD;
                    return Wn;
                })
                .reduce(0L, (a, b) -> (a + b) % MOD);

        long ans = (totalSequences - sumNk + MOD) % MOD;
        return ans;
    }

    public static String solve() {
        return Long.toString(solveF(7500000));
    }

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