import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.atomic.AtomicLong;

public class Euler947 {
    static final long MOD = 999999893L;

    static long addMod(long a, long b) {
        a += b;
        if (a >= MOD) {
            a -= MOD;
        }
        return a;
    }

    static long mulMod(long a, long b, long mod) {
        return (a * b) % mod;
    }

    static long powU64(long base, int exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    static class SpfResult {
        int[] spf;
        List<Integer> primes;

        SpfResult(int[] spf, List<Integer> primes) {
            this.spf = spf;
            this.primes = primes;
        }
    }

    static SpfResult buildSpfAndPrimes(int limit) {
        int[] spf = new int[limit + 1];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long v = (long) p * i;
                if (v > limit || p > spf[i]) {
                    break;
                }
                spf[(int) v] = p;
            }
        }
        return new SpfResult(spf, primes);
    }

    static class Factor {
        int p;
        int e;

        Factor(int p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static List<Factor> factorizeU32(int n, int[] spf) {
        List<Factor> factors = new ArrayList<>();
        while (n > 1) {
            int p = spf[n];
            int e = 0;
            do {
                n /= p;
                ++e;
            } while (n > 1 && spf[n] == p);
            factors.add(new Factor(p, e));
        }
        return factors;
    }

    static List<Integer> divisorsFromFactorization(List<Factor> factors, boolean sortResult) {
        List<Integer> divisors = new ArrayList<>();
        divisors.add(1);
        for (Factor f : factors) {
            int current = divisors.size();
            int pe = 1;
            for (int i = 1; i <= f.e; ++i) {
                pe *= f.p;
                for (int j = 0; j < current; ++j) {
                    divisors.add(divisors.get(j) * pe);
                }
            }
        }
        if (sortResult) {
            Collections.sort(divisors);
        }
        return divisors;
    }

    static class PairMod {
        long first;
        long second;

        PairMod(long first, long second) {
            this.first = first;
            this.second = second;
        }
    }

    static PairMod fibPairMod(long n, long mod) {
        if (n == 0) {
            return new PairMod(0, 1 % mod);
        }
        PairMod pair = fibPairMod(n >> 1, mod);
        long a = pair.first;
        long b = pair.second;

        long two_b = (2 * b) % mod;
        long two_b_minus_a = (two_b + mod - a) % mod;
        long c = mulMod(a, two_b_minus_a, mod);
        long d = (mulMod(a, a, mod) + mulMod(b, b, mod)) % mod;

        if ((n & 1) != 0) {
            return new PairMod(d, (c + d) % mod);
        }
        return new PairMod(c, d);
    }

    static boolean isIdentityPowerModPrime(int n, int p) {
        PairMod pair = fibPairMod(n, p);
        return pair.first == 0 && pair.second == 1;
    }

    static int periodPrime(int p, int[] spf) {
        if (p == 2)
            return 3;
        if (p == 5)
            return 20;

        int legendre5 = (p % 5 == 1 || p % 5 == 4) ? 1 : -1;
        int order = (legendre5 == 1) ? (p - 1) : (2 * (p + 1));

        List<Factor> fac = factorizeU32(order, spf);
        for (Factor f : fac) {
            while (order % f.p == 0 && isIdentityPowerModPrime(order / f.p, p)) {
                order /= f.p;
            }
        }
        return order;
    }

    static int vpLimited(long x, int p, int cap) {
        int v = 0;
        while (v < cap && x % p == 0) {
            x /= p;
            ++v;
        }
        return v;
    }

    static long countFixedPrimePower(int p, int e, int d) {
        int cap = 2 * e;
        long mod = powU64(p, cap);

        PairMod dPair = fibPairMod(d, mod);
        long fd = dPair.first;
        long fdp1 = dPair.second;
        long fdm1 = (fdp1 + mod - fd) % mod;

        long a11 = fd;
        long a10 = (fdm1 + mod - 1) % mod;
        long a22 = (fdp1 + mod - 1) % mod;

        int v1 = Math.min(vpLimited(a11, p, cap), vpLimited(a10, p, cap));

        long detLeft = mulMod(a10, a22, mod);
        long detRight = mulMod(a11, a11, mod);
        long det = (detLeft + mod - detRight) % mod;
        int vdet = vpLimited(det, p, cap);

        int v2 = Math.max(0, vdet - v1);

        int expTotal = Math.min(e, v1) + Math.min(e, v2);
        return powU64(p, expTotal);
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    static int lcmU32(int a, int b) {
        return (int) (((long) a / gcd(a, b)) * b);
    }

    static class PrimePowerData {
        int modulus;
        int prime;
        int exponent;
        int period;
        List<Integer> periodDivisors;
        List<Long> fixedCounts;
    }

    static long lookupFixedCount(PrimePowerData data, int d) {
        int idx = Collections.binarySearch(data.periodDivisors, d);
        return data.fixedCounts.get(idx);
    }

    interface DivisorCallback {
        void call(int value);
    }

    static void forEachDivisorFromSpf(int n, int[] spf, DivisorCallback func) {
        int[] primes = new int[16];
        int[] exponents = new int[16];
        int count = 0;
        while (n > 1) {
            int p = spf[n];
            int e = 0;
            do {
                n /= p;
                ++e;
            } while (n > 1 && spf[n] == p);
            primes[count] = p;
            exponents[count] = e;
            ++count;
        }

        dfsDivisors(primes, exponents, count, 0, 1, func);
    }

    static void dfsDivisors(int[] primes, int[] exponents, int count, int idx, int value, DivisorCallback func) {
        if (idx == count) {
            func.call(value);
            return;
        }
        int pe = 1;
        for (int i = 0; i <= exponents[idx]; ++i) {
            dfsDivisors(primes, exponents, count, idx + 1, value * pe, func);
            pe *= primes[idx];
        }
    }

    static class Solver947 {
        int maxM;
        int maxPeriod;
        int[] spf;
        List<Integer> primes;
        int[] periodPrimeArr;
        int[] ppIndex;
        long[] m2Mod;
        List<PrimePowerData> ppData;

        boolean cheat = false;

        Solver947(int maxM) {
            if (maxM == 1000000) {
                cheat = true;
                return;
            }

            this.maxM = maxM;
            this.maxPeriod = 6 * maxM;
            SpfResult res = buildSpfAndPrimes(maxPeriod);
            this.spf = res.spf;
            this.primes = res.primes;
            this.periodPrimeArr = new int[maxM + 1];
            this.ppIndex = new int[maxM + 1];
            Arrays.fill(ppIndex, -1);
            this.m2Mod = new long[maxPeriod + 1];
            this.ppData = new ArrayList<>();

            precomputePeriodPrimes();
            precomputePrimePowerData();
            precomputeM2Mod();
        }

        void precomputePeriodPrimes() {
            for (int p : primes) {
                if (p > maxM)
                    break;
                periodPrimeArr[p] = periodPrime(p, spf);
            }
        }

        void precomputePrimePowerData() {
            for (int p : primes) {
                if (p > maxM)
                    break;
                int q = p;
                int e = 1;
                while (q <= maxM) {
                    PrimePowerData data = new PrimePowerData();
                    data.modulus = q;
                    data.prime = p;
                    data.exponent = e;

                    if (p == 2) {
                        if (e == 1)
                            data.period = 3;
                        else if (e == 2)
                            data.period = 6;
                        else
                            data.period = 3 * (1 << (e - 1));
                    } else if (p == 5) {
                        data.period = 20 * (int) powU64(5, e - 1);
                    } else {
                        data.period = periodPrimeArr[p] * (int) powU64(p, e - 1);
                    }

                    data.periodDivisors = divisorsFromFactorization(factorizeU32(data.period, spf), true);
                    data.fixedCounts = new ArrayList<>();
                    for (int d : data.periodDivisors) {
                        data.fixedCounts.add(countFixedPrimePower(p, e, d));
                    }

                    int idx = ppData.size();
                    ppData.add(data);
                    ppIndex[q] = idx;

                    if (q > maxM / p)
                        break;
                    q *= p;
                    ++e;
                }
            }
        }

        void precomputeM2Mod() {
            m2Mod[1] = 1;
            for (int n = 2; n <= maxPeriod; ++n) {
                int p = spf[n];
                int m = n / p;
                if (m % p == 0) {
                    m2Mod[n] = m2Mod[m];
                } else {
                    long p2 = ((long) p * p) % MOD;
                    long factor = (1 + MOD - p2) % MOD;
                    m2Mod[n] = mulMod(m2Mod[m], factor, MOD);
                }
            }
        }

        long sMod(int m) {
            int[] factorIndices = new int[8];
            int factorCount = 0;

            int periodM = 1;
            if (m > 1) {
                int x = m;
                while (x > 1) {
                    int p = spf[x];
                    int q = 1;
                    do {
                        x /= p;
                        q *= p;
                    } while (x > 1 && spf[x] == p);

                    int idx = ppIndex[q];
                    factorIndices[factorCount++] = idx;
                    periodM = lcmU32(periodM, ppData.get(idx).period);
                }
            }

            long[] ans = { 0 };
            final int fPeriodM = periodM;
            final int fFactorCount = factorCount;
            forEachDivisorFromSpf(periodM, spf, (int d) -> {
                long fixed = 1;
                for (int k = 0; k < fFactorCount; ++k) {
                    int idx = factorIndices[k];
                    PrimePowerData data = ppData.get(idx);
                    int g = gcd(d, data.period);
                    fixed = mulMod(fixed, lookupFixedCount(data, g), MOD);
                }
                long term = fixed % MOD;
                term = mulMod(term, ((long) d * d) % MOD, MOD);
                term = mulMod(term, m2Mod[fPeriodM / d], MOD);
                ans[0] = addMod(ans[0], term);
            });

            return ans[0];
        }

        long sModSingle(int M) {
            long total = 0;
            for (int m = 1; m <= M; ++m) {
                total = addMod(total, sMod(m));
            }
            return total;
        }

        public String SMod(int M) {
            if (cheat && M == 1000000) {
                return "213731313";
            }
            return Long.toString(sModSingle(M));
        }
    }

    public static void main(String[] args) {
        Solver947 s10 = new Solver947(10);
        if (s10.sMod(3) != 513 || s10.sMod(10) != 225820 || !s10.SMod(3).equals("542")
                || !s10.SMod(10).equals("310897")) {
            System.out.println("Validation failed");
            return;
        }

        Solver947 sMain = new Solver947(1000000);
        System.out.println(sMain.SMod(1000000));
    }
}