import java.util.ArrayList;
import java.util.Arrays;

public class Euler989 {
    private static final long MOD = 1_000_000_009L;
    private static final long TARGET_LIMIT = 100_000_000_000_000L;
    private static final long SAMPLE_LIMIT = 1_000L;
    private static final long SAMPLE_SUM = 190_950_976L;

    private static final long SQRT5_MOD = 383_008_016L;
    private static final long PHI_MOD = 691_504_013L;
    private static final long PSI_MOD = 308_495_997L;

    private static final class Options {
        boolean allowMultithreading = true;
        int requestedThreads = 0;
    }

    private static final class IntList {
        private int[] data = new int[16];
        private int size = 0;

        void add(int value) {
            if (size == data.length) {
                data = Arrays.copyOf(data, data.length * 2);
            }
            data[size++] = value;
        }

        int get(int index) {
            return data[index];
        }

        int size() {
            return size;
        }

        int[] toArray() {
            return Arrays.copyOf(data, size);
        }
    }

    private static final class PowerSeq {
        long v;
        long term;
        long delta;
        long deltaStep;

        PowerSeq(long v, long term, long delta, long deltaStep) {
            this.v = v;
            this.term = term;
            this.delta = delta;
            this.deltaStep = deltaStep;
        }

        static PowerSeq square(long base) {
            long baseSq = modMul(base, base);
            return new PowerSeq(0L, 1L, base, baseSq);
        }

        static PowerSeq triangular(long base) {
            long baseSq = modMul(base, base);
            return new PowerSeq(0L, 1L, baseSq, baseSq);
        }

        void step() {
            term = modMul(term, delta);
            delta = modMul(delta, deltaStep);
            ++v;
        }

        long extendThrough(long target, long window) {
            while (v <= target) {
                window = modAdd(window, term);
                step();
            }
            return window;
        }

        long trimBefore(long target, long window) {
            while (v < target) {
                window = modSub(window, term);
                step();
            }
            return window;
        }
    }

    private static final class PrimitiveWorker implements Runnable {
        long limit;
        int startG;
        int endG;
        byte[] mu;
        int[] phiSq;
        int[] phiInvSq;
        long phiTotal;
        long psiTotal;

        @Override
        public void run() {
            long localPhi = 0L;
            long localPsi = 0L;
            for (int g = startG; g < endG; ++g) {
                int muG = mu[g];
                if (muG == 0) {
                    continue;
                }

                long gg = (long) g * (long) g;
                long scaledLimit = limit / gg;

                long phiW = phiSq[g] & 0xFFFFFFFFL;
                long phiWInv = phiInvSq[g] & 0xFFFFFFFFL;
                long psiW = (g & 1) == 0 ? phiWInv : modNeg(phiWInv);
                long psiWInv = (g & 1) == 0 ? phiW : modNeg(phiW);

                long phiValue = nonprimitiveSum(scaledLimit, phiW, phiWInv);
                long psiValue = nonprimitiveSum(scaledLimit, psiW, psiWInv);

                if (muG > 0) {
                    localPhi += phiValue;
                    localPsi += psiValue;
                } else {
                    localPhi -= phiValue;
                    localPsi -= psiValue;
                }
            }
            phiTotal = localPhi;
            psiTotal = localPsi;
        }
    }

    private static void usage() {
        System.err.println(
                "Usage:\n"
                        + "  java Euler989 [--skip-checkpoints]\n"
                        + "  java Euler989 validate [check_max] [--single-thread] [--threads=N]\n"
                        + "  java Euler989 sum <limit> [--single-thread] [--threads=N]\n"
                        + "  java Euler989 answer [--single-thread] [--threads=N]");
    }

    private static long modMul(long a, long b) {
        return (a * b) % MOD;
    }

    private static long modAdd(long a, long b) {
        long s = a + b;
        return s >= MOD ? s - MOD : s;
    }

    private static long modSub(long a, long b) {
        return a >= b ? a - b : a + MOD - b;
    }

    private static long modNeg(long a) {
        return a == 0L ? 0L : MOD - a;
    }

    private static long modPow(long base, long exp) {
        long result = 1L;
        long cur = base % MOD;
        while (exp > 0L) {
            if ((exp & 1L) != 0L) {
                result = modMul(result, cur);
            }
            cur = modMul(cur, cur);
            exp >>= 1;
        }
        return result;
    }

    private static long isqrt(long n) {
        long x = (long) Math.sqrt((double) n);
        while ((x + 1L) <= n / (x + 1L)) {
            ++x;
        }
        while (x > n / x) {
            --x;
        }
        return x;
    }

    private static int[] sievePrimes(int limit) {
        if (limit < 2) {
            return new int[0];
        }
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        IntList primes = new IntList();
        for (int i = 2; i <= limit; ++i) {
            if (!isPrime[i]) {
                continue;
            }
            primes.add(i);
            if (i > limit / i) {
                continue;
            }
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
        return primes.toArray();
    }

    private static byte[] mobiusSieve(int limit) {
        byte[] mu = new byte[limit + 1];
        int[] least = new int[limit + 1];
        IntList primes = new IntList();
        mu[1] = 1;

        for (int i = 2; i <= limit; ++i) {
            if (least[i] == 0) {
                least[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            int li = least[i];
            byte mui = mu[i];
            for (int idx = 0; idx < primes.size(); ++idx) {
                int p = primes.get(idx);
                long ip = (long) i * (long) p;
                if (ip > limit || p > li) {
                    break;
                }
                least[(int) ip] = p;
                if (p == li) {
                    mu[(int) ip] = 0;
                    break;
                }
                mu[(int) ip] = (byte) (-mui);
            }
        }

        return mu;
    }

    private static int gBruteforce(long n) {
        int count = 0;
        for (long x = 0; x < n; ++x) {
            if ((x * x + n - x - 1L) % n == 0L) {
                ++count;
            }
        }
        return count;
    }

    private static int gFromFactorization(long n, int[] primes) {
        if (n == 1L) {
            return 1;
        }

        int result = 1;
        for (int p32 : primes) {
            long p = p32;
            if (p > n / p) {
                break;
            }
            if (n % p != 0L) {
                continue;
            }

            int exponent = 0;
            while (n % p == 0L) {
                n /= p;
                ++exponent;
            }

            if (p == 2L) {
                return 0;
            }
            if (p == 5L) {
                if (exponent >= 2) {
                    return 0;
                }
                continue;
            }

            long r = p % 5L;
            if (r == 1L || r == 4L) {
                result *= 2;
            } else if (r == 2L || r == 3L) {
                return 0;
            } else {
                throw new IllegalStateException("unreachable");
            }
        }

        if (n > 1L) {
            if (n == 2L) {
                return 0;
            }
            if (n == 5L) {
                return result;
            }
            long r = n % 5L;
            if (r == 1L || r == 4L) {
                result *= 2;
            } else if (r == 2L || r == 3L) {
                return 0;
            } else {
                throw new IllegalStateException("unreachable");
            }
        }

        return result;
    }

    private static long qForm(long a, long b) {
        return a * a - a * b - b * b;
    }

    private static long gcd(long a, long b) {
        while (b != 0L) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    private static int reducedPairCount(long n) {
        int count = 0;
        long maxB = isqrt(n);
        for (long b = 1L; b <= maxB; ++b) {
            for (long a = 2L * b;; ++a) {
                long q = qForm(a, b);
                if (q > n) {
                    break;
                }
                if (q == n && gcd(a, b) == 1L) {
                    ++count;
                }
            }
        }
        return count;
    }

    private static long directPairSum(long limit, long base) {
        long acc = 0L;
        long maxB = isqrt(limit);
        for (long b = 1L; b <= maxB; ++b) {
            for (long a = 2L * b;; ++a) {
                long q = qForm(a, b);
                if (q > limit) {
                    break;
                }
                if (gcd(a, b) == 1L) {
                    acc = modAdd(acc, modPow(base, q));
                }
            }
        }
        return acc;
    }

    private static long nonprimitiveSum(long limit, long w, long winv) {
        if (limit == 0L) {
            return 0L;
        }

        long sqrtLimit = isqrt(limit);
        long winv5 = modPow(winv, 5L);
        long winv10 = modMul(winv5, winv5);
        long ans = 0L;

        long evenTMax = sqrtLimit / 2L;
        if (evenTMax > 0L) {
            PowerSeq addSeq = PowerSeq.square(w);
            PowerSeq trimSeq = PowerSeq.square(w);
            long window = 0L;
            long factor = 1L;
            long ratio = winv5;

            for (long t = 1L; t <= evenTMax; ++t) {
                factor = modMul(factor, ratio);
                ratio = modMul(ratio, winv10);

                long vmax = isqrt(limit + 5L * t * t);
                window = addSeq.extendThrough(vmax, window);
                window = trimSeq.trimBefore(3L * t, window);
                ans = modAdd(ans, modMul(factor, window));
            }
        }

        long oddTMax = (sqrtLimit - 1L) / 2L;
        PowerSeq addSeq = PowerSeq.triangular(w);
        PowerSeq trimSeq = PowerSeq.triangular(w);
        long window = 0L;
        long factor = winv;
        long ratio = winv10;

        for (long t = 0L; t <= oddTMax; ++t) {
            long disc = 4L * limit + 20L * t * t + 20L * t + 5L;
            long vmax = (isqrt(disc) - 1L) / 2L;
            window = addSeq.extendThrough(vmax, window);
            window = trimSeq.trimBefore(3L * t + 1L, window);
            ans = modAdd(ans, modMul(factor, window));
            factor = modMul(factor, ratio);
            ratio = modMul(ratio, winv10);
        }

        return ans;
    }

    private static int[] squarePowers(long base, int maxG) {
        int[] out = new int[maxG + 1];
        out[0] = 1;
        if (maxG == 0) {
            return out;
        }

        long baseSq = modMul(base, base);
        long value = 1L;
        long ratio = base;
        for (int g = 1; g <= maxG; ++g) {
            value = modMul(value, ratio);
            out[g] = (int) value;
            ratio = modMul(ratio, baseSq);
        }
        return out;
    }

    private static long normalizeSignedMod(long value) {
        long res = value % MOD;
        if (res < 0L) {
            res += MOD;
        }
        return res;
    }

    private static int chooseThreadCount(boolean allowMultithreading, int requestedThreads, int workload) {
        if (!allowMultithreading || workload <= 1) {
            return 1;
        }

        int threads = requestedThreads;
        if (threads == 0) {
            threads = Runtime.getRuntime().availableProcessors();
            if (threads == 0) {
                threads = 1;
            }
        }
        if (threads > workload) {
            threads = workload;
        }
        return Math.max(1, threads);
    }

    private static long[] primitiveSums(long limit, byte[] mu, int[] phiSq, int[] phiInvSq, Options options)
            throws InterruptedException {
        int maxG = (int) isqrt(limit);
        int threadCount = chooseThreadCount(options.allowMultithreading, options.requestedThreads, maxG);

        PrimitiveWorker[] tasks = new PrimitiveWorker[threadCount];
        Thread[] threads = new Thread[threadCount];

        for (int t = 0; t < threadCount; ++t) {
            PrimitiveWorker task = new PrimitiveWorker();
            task.limit = limit;
            task.startG = 1 + (int) (((long) maxG * (long) t) / (long) threadCount);
            task.endG = 1 + (int) (((long) maxG * (long) (t + 1)) / (long) threadCount);
            task.mu = mu;
            task.phiSq = phiSq;
            task.phiInvSq = phiInvSq;
            tasks[t] = task;
            threads[t] = new Thread(task);
            threads[t].start();
        }

        long phiTotal = 0L;
        long psiTotal = 0L;
        for (int t = 0; t < threadCount; ++t) {
            threads[t].join();
            phiTotal += tasks[t].phiTotal;
            psiTotal += tasks[t].psiTotal;
        }

        return new long[] { normalizeSignedMod(phiTotal), normalizeSignedMod(psiTotal) };
    }

    private static long solve(long limit, Options options) throws InterruptedException {
        int maxG = (int) isqrt(limit);
        byte[] mu = mobiusSieve(maxG);

        long phiInv = modPow(PHI_MOD, MOD - 2L);
        int[] phiSq = squarePowers(PHI_MOD, maxG);
        int[] phiInvSq = squarePowers(phiInv, maxG);

        long[] sums = primitiveSums(limit, mu, phiSq, phiInvSq, options);
        long invSqrt5 = modPow(SQRT5_MOD, MOD - 2L);
        return modMul(modSub(sums[0], sums[1]), invSqrt5);
    }

    private static long checksumViaFactorization(long limit, int[] primes) {
        long acc = 0L;
        long fPrev = 0L;
        long fCur = 1L;
        for (long n = 1L; n <= limit; ++n) {
            long g = gFromFactorization(n, primes);
            acc = modAdd(acc, modMul(fCur, g));
            long fNext = modAdd(fPrev, fCur);
            fPrev = fCur;
            fCur = fNext;
        }
        return acc;
    }

    private static void require(boolean condition, String message) {
        if (!condition) {
            throw new IllegalStateException(message);
        }
    }

    private static void runCheckpoints(Options options) throws InterruptedException {
        require(modMul(SQRT5_MOD, SQRT5_MOD) == 5L, "sqrt(5) mismatch");
        require(modSub(modMul(PHI_MOD, PHI_MOD), PHI_MOD) == 1L, "phi mismatch");
        require(modSub(modMul(PSI_MOD, PSI_MOD), PSI_MOD) == 1L, "psi mismatch");
        require(modMul(PHI_MOD, PSI_MOD) == MOD - 1L, "phi*psi mismatch");

        int checkMax = 250;
        int[] primes = sievePrimes((int) isqrt(checkMax) + 10);
        for (long n = 1L; n <= checkMax; ++n) {
            require(gBruteforce(n) == gFromFactorization(n, primes), "factorization mismatch");
            require(reducedPairCount(n) == gFromFactorization(n, primes), "pair-count mismatch");
        }

        long directLimit = Math.min(checkMax, 250);
        long phiPairSum = directPairSum(directLimit, PHI_MOD);
        long psiPairSum = directPairSum(directLimit, PSI_MOD);
        int maxG = (int) isqrt(directLimit);
        byte[] mu = mobiusSieve(maxG);
        long phiInv = modPow(PHI_MOD, MOD - 2L);
        int[] phiSq = squarePowers(PHI_MOD, maxG);
        int[] phiInvSq = squarePowers(phiInv, maxG);
        long[] fast = primitiveSums(directLimit, mu, phiSq, phiInvSq, options);
        require(fast[0] == phiPairSum, "phi pair sum mismatch");
        require(fast[1] == psiPairSum, "psi pair sum mismatch");

        int[] samplePrimes = sievePrimes((int) isqrt(SAMPLE_LIMIT) + 10);
        long sampleFast = solve(SAMPLE_LIMIT, options);
        long sampleFactorized = checksumViaFactorization(SAMPLE_LIMIT, samplePrimes);
        require(sampleFast == SAMPLE_SUM, "sample sum mismatch");
        require(sampleFast == sampleFactorized, "sample factorization mismatch");
    }

    private static boolean parseU64(String text, long[] out) {
        if (text.isEmpty()) {
            return false;
        }
        long value = 0L;
        for (int i = 0; i < text.length(); ++i) {
            char c = text.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }
            value = value * 10L + (long) (c - '0');
        }
        out[0] = value;
        return true;
    }

    private static boolean parseCommandOptions(String[] args, int startIndex, Options options, ArrayList<String> positional) {
        for (int i = startIndex; i < args.length; ++i) {
            String arg = args[i];
            if ("--single-thread".equals(arg)) {
                options.allowMultithreading = false;
                continue;
            }
            if ("--single-process".equals(arg)) {
                options.allowMultithreading = false;
                continue;
            }
            if (arg.startsWith("--threads=")) {
                String tail = arg.substring("--threads=".length());
                if (tail.isEmpty()) {
                    return false;
                }
                try {
                    options.requestedThreads = Integer.parseInt(tail);
                } catch (NumberFormatException ex) {
                    return false;
                }
                continue;
            }
            if (arg.startsWith("--processes=")) {
                String tail = arg.substring("--processes=".length());
                if (tail.isEmpty()) {
                    return false;
                }
                try {
                    options.requestedThreads = Integer.parseInt(tail);
                } catch (NumberFormatException ex) {
                    return false;
                }
                continue;
            }
            positional.add(arg);
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        Options options = new Options();
        ArrayList<String> positional = new ArrayList<>();

        boolean skipCheckpoints = false;
        ArrayList<String> cleaned = new ArrayList<>();
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                skipCheckpoints = true;
            } else {
                cleaned.add(arg);
            }
        }
        args = cleaned.toArray(new String[0]);

        if (!skipCheckpoints) {
            runCheckpoints(options);
        }

        if (args.length == 0) {
            System.out.println(solve(TARGET_LIMIT, options));
            return;
        }

        String command = args[0];
        options = new Options();
        positional.clear();
        if (!parseCommandOptions(args, 1, options, positional)) {
            usage();
            return;
        }

        if ("validate".equals(command)) {
            long checkMax = 250L;
            if (positional.size() > 1) {
                usage();
                return;
            }
            if (positional.size() == 1) {
                long[] parsed = new long[1];
                if (!parseU64(positional.get(0), parsed)) {
                    usage();
                    return;
                }
                checkMax = parsed[0];
            }
            int[] primes = sievePrimes((int) isqrt(checkMax) + 10);
            for (long n = 1L; n <= checkMax; ++n) {
                require(gBruteforce(n) == gFromFactorization(n, primes), "factorization mismatch");
                require(reducedPairCount(n) == gFromFactorization(n, primes), "pair-count mismatch");
            }
            System.out.println("ok");
            return;
        }

        if ("sum".equals(command) && positional.size() == 1) {
            long[] parsed = new long[1];
            if (!parseU64(positional.get(0), parsed)) {
                usage();
                return;
            }
            System.out.println(solve(parsed[0], options));
            return;
        }

        if ("answer".equals(command) && positional.isEmpty()) {
            System.out.println(solve(TARGET_LIMIT, options));
            return;
        }

        usage();
    }
}