public class Euler652 {
    static final long kTargetN = 1000000000000000000L;
    static final long kMod = 1000000000L;

    static int floorLog2(long x) {
        int r = 0;
        while (x > 1) {
            x >>= 1;
            ++r;
        }
        return r;
    }

    static boolean powLeq(long base, int exp, long limit) {
        long res = 1;
        // avoid overflow carefully
        for (int i = 0; i < exp; ++i) {
            // maxLimit / base
            if (res > (limit / base))
                return false;
            long test = res * base;
            if (test > limit || test < 0)
                return false;
            res = test;
        }
        return true;
    }

    static long intNthRoot(long n, int k) {
        if (k == 1 || n <= 1)
            return n;
        long approx = (long) Math.pow((double) n, 1.0 / k);
        long r = Math.max(1L, approx);
        while (powLeq(r + 1, k, n))
            ++r;
        while (!powLeq(r, k, n))
            --r;
        return r;
    }

    static int[] mobiusSieve(int nmax) {
        int[] mu = new int[nmax + 1];
        java.util.ArrayList<Integer> primes = new java.util.ArrayList<>();
        mu[1] = 1;
        int[] spf = new int[nmax + 1];
        for (int i = 2; i <= nmax; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                long v = (long) p * i;
                if (v > nmax)
                    break;
                spf[(int) v] = p;
                if (i % p == 0) {
                    mu[(int) v] = 0;
                    break;
                }
                mu[(int) v] = -mu[i];
            }
        }
        return mu;
    }

    static long powerFreeCountUpto(long M, int[] mu) {
        if (M < 2)
            return 0;
        int L = floorLog2(M);
        int max_d = Math.min(L, mu.length - 1);
        long total = 0;
        for (int d = 1; d <= max_d; ++d) {
            int md = mu[d];
            if (md == 0)
                continue;
            long root = intNthRoot(M, d);
            if (root >= 2) {
                total += (long) md * (root - 1);
            }
        }
        return total;
    }

    static long[][] buildCoprimeTable(int L, int[] mu) {
        long[][] F = new long[L + 1][L + 1];
        for (int A = 1; A <= L; ++A) {
            for (int B = 1; B <= L; ++B) {
                int m = Math.min(A, B);
                long total = 0;
                for (int d = 1; d <= m; ++d) {
                    int md = mu[d];
                    if (md == 0)
                        continue;
                    total += (long) md * (A / d) * (B / d);
                }
                F[A][B] = total;
            }
        }
        return F;
    }

    static long[] buildCountA(long N, int[] mu, int L) {
        long[] roots = new long[L + 2];
        for (int k = 1; k <= L; ++k) {
            roots[k] = intNthRoot(N, k);
        }
        roots[L + 1] = 1;

        long[] pf = new long[L + 2];
        for (int k = 1; k <= L + 1; ++k) {
            pf[k] = powerFreeCountUpto(roots[k], mu);
        }

        long[] countA = new long[L + 1];
        for (int A = 1; A <= L; ++A) {
            countA[A] = pf[A] - pf[A + 1];
        }
        return countA;
    }

    static long computeDMod(long N, long mod) {
        int L = floorLog2(N);
        int[] mu = mobiusSieve(L);
        long[][] coprime = buildCoprimeTable(L, mu);
        long[] countA = buildCountA(N, mu, L);

        long irrational = 0;
        for (int A = 1; A <= L; ++A) {
            long ca = countA[A];
            if (ca == 0)
                continue;
            long ca_mod = ca % mod;
            for (int B = 1; B <= L; ++B) {
                long cb = countA[B];
                if (cb == 0)
                    continue;
                long pairs = 0;
                if (A == B) {
                    if (ca < 2)
                        continue;
                    pairs = (ca_mod * ((ca - 1) % mod)) % mod;
                } else {
                    pairs = (ca_mod * (cb % mod)) % mod;
                }
                long term = (pairs * (coprime[A][B] % mod)) % mod;
                irrational = (irrational + term) % mod;
            }
        }
        long rational = coprime[L][L] % mod;
        return (rational + irrational) % mod;
    }

    public static String solve() {
        long N = kTargetN;
        long ans = computeDMod(N, kMod);
        return String.format("%09d", ans);
    }

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