import java.util.ArrayList;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler850 {
    static final long MOD = 977676779L;

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

    static long mulMod(long a, long b, long mod) {
        java.math.BigInteger biA = java.math.BigInteger.valueOf(a);
        java.math.BigInteger biB = java.math.BigInteger.valueOf(b);
        java.math.BigInteger biMod = java.math.BigInteger.valueOf(mod);
        return biA.multiply(biB).remainder(biMod).longValue();
    }

    static long normI128Mod(java.math.BigInteger x, long mod) {
        java.math.BigInteger biMod = java.math.BigInteger.valueOf(mod);
        java.math.BigInteger r = x.remainder(biMod);
        if (r.compareTo(java.math.BigInteger.ZERO) < 0) {
            r = r.add(biMod);
        }
        return r.longValue();
    }

    static long isqrt(long x) {
        long lo = 0;
        long hi = (x < (1L << 32)) ? (1L << 32) : x;
        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid <= x / mid) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    static ArrayList<Long> primesUpTo(int n) {
        int[] lp = new int[n + 1];
        ArrayList<Long> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add((long) i);
            }
            for (long p : primes) {
                if (p * i > n || p > lp[i])
                    break;
                lp[(int) (p * i)] = (int) p;
            }
        }
        return primes;
    }

    static class Solver850 {
        long N;
        long mod2;
        long oddHalf;
        ArrayList<Long> primes;
        int primeLimit;

        Solver850(long n, long mod) {
            this.N = n;
            this.mod2 = 2 * mod;
            this.oddHalf = (n + 1) / 2;

            int lim = (int) isqrt(N) + 1;
            this.primes = primesUpTo(lim);
            this.primeLimit = 0;
            while (primeLimit < primes.size() && primes.get(primeLimit) * primes.get(primeLimit) <= N) {
                primeLimit++;
            }
        }

        long computeTMod() {
            ArrayList<Long> ps = new ArrayList<>();
            ArrayList<Integer> es = new ArrayList<>();
            long hMod = contribute(1L, 1L, ps, es, -1, 1L);
            hMod = addMod(hMod, computeBranchesMod(), mod2);

            java.math.BigInteger bn = java.math.BigInteger.valueOf(N);
            java.math.BigInteger sumNModBase = bn.multiply(bn.add(java.math.BigInteger.ONE))
                    .divide(java.math.BigInteger.valueOf(2));
            long sumNMod = sumNModBase.remainder(java.math.BigInteger.valueOf(mod2)).longValue();
            long aMod = mulMod(oddHalf % mod2, sumNMod, mod2);

            if (aMod >= hMod)
                return aMod - hMod;
            return aMod + mod2 - hMod;
        }

        long contribute(long prd, long rad, ArrayList<Long> ps, ArrayList<Integer> es, int maxE, long phiMod) {
            long Np = N / prd;
            int K = maxE + 2;
            long shift = K / 2;

            java.math.BigInteger base1 = java.math.BigInteger.valueOf(Np / rad);
            java.math.BigInteger base2 = java.math.BigInteger.valueOf(oddHalf - shift);
            java.math.BigInteger base = base1.multiply(base2);
            long ret = normI128Mod(base, mod2);

            for (int k = K - (K & 1) - 2; k > 0; k -= 2) {
                long newr = 1;
                boolean over = false;
                for (int i = 0; i < ps.size(); ++i) {
                    long p = ps.get(i);
                    int need = es.get(i) / k + 1;
                    for (int t = 0; t < need; ++t) {
                        if (newr > Np / p) {
                            over = true;
                            break;
                        }
                        newr *= p;
                    }
                    if (over)
                        break;
                }
                if (over)
                    break;

                ret += Np / newr;
                ret %= mod2;
            }

            return mulMod(ret, phiMod, mod2);
        }

        long rec(int ind, long prd, long rad, ArrayList<Long> ps, ArrayList<Integer> es, int maxE, long phiMod) {
            long ret = contribute(prd, rad, ps, es, maxE, phiMod);

            for (int i = ind; i < primeLimit; ++i) {
                long p = primes.get(i);
                if (prd > N / p || rad > N / p)
                    break;
                long nxtPrd = prd * p;
                long nxtRad = rad * p;
                long prdLim = N / nxtRad;
                if (nxtPrd > prdLim)
                    break;

                ps.add(p);
                es.add(-1);

                long curPrd = nxtPrd;
                long phiEMod = phiMod;
                while (curPrd <= prdLim) {
                    int e = es.get(es.size() - 1) + 1;
                    es.set(es.size() - 1, e);
                    if (e == 0) {
                        phiEMod = mulMod(phiMod, (p - 1) % mod2, mod2);
                    } else {
                        phiEMod = mulMod(phiEMod, p % mod2, mod2);
                    }

                    int childMax = Math.max(maxE, e);
                    ret = addMod(ret, rec(i + 1, curPrd, nxtRad, ps, es, childMax, phiEMod), mod2);

                    if (curPrd > prdLim / p)
                        break;
                    curPrd *= p;
                }

                ps.remove(ps.size() - 1);
                es.remove(es.size() - 1);
            }

            return ret;
        }

        long branchFromPrime(int idx) {
            long p = primes.get(idx);
            if (p > N / p)
                return 0;

            long prdLim = N / p;
            if (p > prdLim)
                return 0;

            ArrayList<Long> ps = new ArrayList<>();
            ps.add(p);
            ArrayList<Integer> es = new ArrayList<>();
            es.add(-1);

            long ret = 0;
            long curPrd = p;
            long phiEMod = 1;

            while (curPrd <= prdLim) {
                int e = es.get(0) + 1;
                es.set(0, e);
                if (e == 0) {
                    phiEMod = (p - 1) % mod2;
                } else {
                    phiEMod = mulMod(phiEMod, p % mod2, mod2);
                }

                ret = addMod(ret, rec(idx + 1, curPrd, p, ps, es, e, phiEMod), mod2);

                if (curPrd > prdLim / p)
                    break;
                curPrd *= p;
            }

            return ret;
        }

        long computeBranchesMod() {
            int cores = Runtime.getRuntime().availableProcessors();
            Thread[] threads = new Thread[cores];
            long[] partials = new long[cores];
            AtomicInteger nextIdx = new AtomicInteger(0);

            for (int t = 0; t < cores; ++t) {
                final int tid = t;
                threads[t] = new Thread(() -> {
                    long local = 0;
                    while (true) {
                        int idx = nextIdx.getAndIncrement();
                        if (idx >= primeLimit)
                            break;
                        local = addMod(local, branchFromPrime(idx), mod2);
                    }
                    partials[tid] = local;
                });
                threads[t].start();
            }

            long total = 0;
            for (int t = 0; t < cores; ++t) {
                try {
                    threads[t].join();
                    total = addMod(total, partials[t], mod2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

            return total;
        }
    }

    public static String solve() {
        long N = 33557799775533L;
        Solver850 solver = new Solver850(N, MOD);
        long tMod = solver.computeTMod();
        long ans = (tMod - (tMod & 1L)) / 2L;
        return Long.toString(ans % MOD);
    }

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