import java.util.ArrayList;
import java.util.List;

public class Euler1007 {
    private static final long MOD = 1_000_000_009L;
    private static final int TARGET = 10_000_000;

    private static long normalize(long value) {
        value %= MOD;
        return value < 0 ? value + MOD : value;
    }

    private static long multiplyMod(long lhs, long rhs) {
        return lhs * rhs % MOD;
    }

    private static long modPow(long base, long exponent) {
        long result = 1;
        while (exponent > 0) {
            if ((exponent & 1L) != 0) {
                result = multiplyMod(result, base);
            }
            base = multiplyMod(base, base);
            exponent >>= 1;
        }
        return result;
    }

    private static long alternatingSum(int n) {
        long inverseFour = modPow(4, MOD - 2);

        // Every quotient-ring value is represented by constant + root * r,
        // with r^2 = r + 1.  Keeping the components in primitive locals avoids
        // allocating temporary objects in the ten-million-step loop.
        long aScaled = 1;
        long bConstant = 1;
        long bRoot = 0;
        long cOlderConstant = 0;
        long cOlderRoot = 0;
        long cPreviousConstant = 1;
        long cPreviousRoot = 0;
        long resultConstant = 0;
        long resultRoot = 0;
        long factorial = 1;

        for (long m = 1; m <= (long) n + 1; ++m) {
            long linearFactor = normalize(4 * m - 6);
            long mMod = m % MOD;

            long aNext = multiplyMod(linearFactor, aScaled);

            // r(a + br) = b + (a + b)r.
            long bNextConstant = multiplyMod(linearFactor, bRoot);
            long bNextRoot = multiplyMod(linearFactor, normalize(bConstant + bRoot));

            // (r + 1)(a + br) = (a + b) + (a + 2b)r.
            long cNextConstant = multiplyMod(
                    linearFactor, normalize(cPreviousConstant + cPreviousRoot));
            long cNextRoot = multiplyMod(
                    linearFactor, normalize(cPreviousConstant + 2 * cPreviousRoot));

            long quadraticFactor = multiplyMod(
                    normalize(16 * normalize(m - 3)), normalize(m - 1));
            // Subtract quadraticFactor * r * cOlder.
            cNextConstant = normalize(
                    cNextConstant - multiplyMod(quadraticFactor, cOlderRoot));
            cNextRoot = normalize(
                    cNextRoot
                            - multiplyMod(
                                    quadraticFactor,
                                    normalize(cOlderConstant + cOlderRoot)));

            // Build n_m.  Here (r-1)(a+br) = (b-a) + ar.
            long numeratorConstant = normalize(
                    -aNext
                            - multiplyMod(mMod, aScaled)
                            + bNextConstant
                            + multiplyMod(mMod, normalize(bRoot - bConstant))
                            - cNextConstant);
            long numeratorRoot = normalize(
                    multiplyMod(mMod, aScaled)
                            + bNextRoot
                            + multiplyMod(mMod, bConstant)
                            - cNextRoot);
            if (m == 1) {
                numeratorConstant = normalize(numeratorConstant + 2);
                numeratorRoot = normalize(numeratorRoot + 2);
            }

            // Subtract 2m(2-r)u_{m-1};
            // (2-r)(a+br) = (2a-b) + (b-a)r.
            long twiceM = 2 * mMod % MOD;
            long adjustedConstant = normalize(
                    numeratorConstant
                            - multiplyMod(
                                    twiceM,
                                    normalize(2 * resultConstant - resultRoot)));
            long adjustedRoot = normalize(
                    numeratorRoot
                            - multiplyMod(
                                    twiceM,
                                    normalize(resultRoot - resultConstant)));

            // u_m = (2-r) * adjusted / 4.
            long resultNextConstant = multiplyMod(
                    normalize(2 * adjustedConstant - adjustedRoot), inverseFour);
            long resultNextRoot = multiplyMod(
                    normalize(adjustedRoot - adjustedConstant), inverseFour);

            aScaled = aNext;
            bConstant = bNextConstant;
            bRoot = bNextRoot;
            cOlderConstant = cPreviousConstant;
            cOlderRoot = cPreviousRoot;
            cPreviousConstant = cNextConstant;
            cPreviousRoot = cNextRoot;
            resultConstant = resultNextConstant;
            resultRoot = resultNextRoot;
            factorial = multiplyMod(factorial, mMod);
        }

        return multiplyMod(resultRoot, modPow(factorial, MOD - 2));
    }

    private static List<Long> bruteValues(
            List<Long> fibonacci, int begin, int end) {
        if (end - begin == 1) {
            return List.of(fibonacci.get(begin));
        }

        List<Long> values = new ArrayList<>();
        for (int split = begin + 1; split < end; ++split) {
            List<Long> left = bruteValues(fibonacci, begin, split);
            List<Long> right = bruteValues(fibonacci, split, end);
            for (long lhs : left) {
                for (long rhs : right) {
                    values.add(lhs - rhs);
                }
            }
        }
        return values;
    }

    private static long bruteAlternatingSum(int n) {
        List<Long> fibonacci = new ArrayList<>();
        for (int i = 0; i <= n; ++i) {
            fibonacci.add(0L);
        }
        if (n >= 1) {
            fibonacci.set(1, 1L);
        }
        for (int index = 2; index <= n; ++index) {
            fibonacci.set(index, fibonacci.get(index - 1) + fibonacci.get(index - 2));
        }

        long total = 0;
        for (long value : bruteValues(fibonacci, 0, n + 1)) {
            total = normalize(total + value);
        }
        return total;
    }

    private static void requireCheckpoint(boolean condition, String description) {
        if (!condition) {
            throw new AssertionError("checkpoint failed: " + description);
        }
    }

    private static void runCheckpoints() {
        for (int n = 0; n <= 10; ++n) {
            requireCheckpoint(
                    alternatingSum(n) == bruteAlternatingSum(n),
                    "brute force comparison for n=" + n);
        }

        requireCheckpoint(alternatingSum(3) == normalize(-6), "published A(3)");
        requireCheckpoint(alternatingSum(10) == normalize(-177_666), "published A(10)");
        requireCheckpoint(alternatingSum(100) == 71_792_794, "published A(100)");
    }

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