import java.util.*;

public class Euler639 {
    static final int MOD = 1000000007;

    static int modPow(long a, long e) {
        long r = 1 % MOD;
        a %= MOD;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return (int) r;
    }

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

    static int subMod(int a, int b) {
        int s = a - b;
        if (s < 0)
            s += MOD;
        return s;
    }

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

    static ArrayList<Integer> primesUpTo(int n) {
        ArrayList<Integer> primes = new ArrayList<>();
        if (n < 2)
            return primes;
        boolean[] comp = new boolean[n + 1];
        comp[0] = comp[1] = true;
        for (int i = 2; i <= n; i++) {
            if (comp[i])
                continue;
            primes.add(i);
            if ((long) i * i <= n) {
                for (int j = i * i; j <= n; j += i)
                    comp[j] = true;
            }
        }
        return primes;
    }

    static class FaulhaberData {
        int K;
        int[][] coeff;

        FaulhaberData(int maxK) {
            K = maxK;
            coeff = new int[K + 1][];
            int[] fact = new int[K + 2];
            int[] invFact = new int[K + 2];
            int[] inv = new int[K + 3];

            Arrays.fill(fact, 1);
            for (int i = 1; i <= K + 1; ++i)
                fact[i] = mulMod(fact[i - 1], i);
            invFact[K + 1] = modPow(fact[K + 1], MOD - 2);
            for (int i = K + 1; i >= 1; --i)
                invFact[i - 1] = mulMod(invFact[i], i);
            for (int i = 1; i <= K + 2; ++i)
                inv[i] = modPow(i, MOD - 2);

            int[] B = new int[K + 1];
            B[0] = 1;
            if (K >= 1)
                B[1] = (MOD + 1) / 2;

            for (int k = 2; k <= K; k += 2) {
                int s = 0;
                for (int i = 0; i < k; ++i) {
                    int t = mulMod(ncr(k, i, fact, invFact), B[i]);
                    t = mulMod(t, inv[k - i + 1]);
                    s = addMod(s, t);
                }
                B[k] = subMod(1, s);
            }

            for (int k = 1; k <= K; ++k) {
                int[] v = new int[k + 2];
                for (int i = 1; i < k; ++i) {
                    int t = B[k + 1 - i];
                    t = mulMod(t, ncr(k, i, fact, invFact));
                    t = mulMod(t, inv[k + 1 - i]);
                    v[i] = t;
                }
                v[k] = (MOD + 1) / 2;
                v[k + 1] = inv[k + 1];
                coeff[k] = v;
            }
        }

        int ncr(int n, int r, int[] fact, int[] invFact) {
            if (r < 0 || r > n)
                return 0;
            return mulMod(mulMod(fact[n], invFact[r]), invFact[n - r]);
        }

        int eval(long n, int k) {
            int[] v = coeff[k];
            int nMod = (int) (n % MOD);
            int m = 1;
            int acc = 0;
            for (int c : v) {
                acc = addMod(acc, mulMod(m, c));
                m = mulMod(m, nMod);
            }
            return acc;
        }
    }

    static class ValData {
        ArrayList<Integer> primes;
        ArrayList<Long>[] V;
    }

    static void collectPowerful(ArrayList<Long> out, long m, int i, long n, ArrayList<Integer> primes) {
        out.add(m);
        if (primes.get(i) * m > n)
            return;
        collectPowerful(out, m * primes.get(i), i, n, primes);
        int lP = primes.size();
        for (int j = i + 1; j < lP; ++j) {
            long p = primes.get(j);
            long mm = m * p * p;
            if (mm > n)
                return;
            collectPowerful(out, mm, j, n, primes);
        }
    }

    @SuppressWarnings("unchecked")
    static ValData buildValData(long n) {
        int lim = (int) Math.sqrt(n);
        ArrayList<Integer> P = primesUpTo(lim);
        int lP = P.size();
        ArrayList<Long>[] V = new ArrayList[lP + 1];
        V[lP] = new ArrayList<>();
        V[lP].add(n);

        HashSet<Long> S = new HashSet<>();
        for (int i = lP - 1; i >= 0; --i) {
            ArrayList<Long> arr = new ArrayList<>();
            arr.add(1L);
            long p = P.get(i);
            collectPowerful(arr, p * p, i, n, P);
            for (long x : arr)
                S.add(n / x);
            ArrayList<Long> cur = new ArrayList<>(S);
            Collections.sort(cur, Collections.reverseOrder());
            V[i] = cur;
        }

        ValData res = new ValData();
        res.primes = P;
        res.V = V;
        return res;
    }

    static int solveTotal(long n, int K) {
        FaulhaberData F = new FaulhaberData(K);
        ValData data = buildValData(n);
        ArrayList<Integer> P = data.primes;
        ArrayList<Long>[] V = data.V;
        int lP = P.size();
        ArrayList<Long> V0 = V[0];

        HashMap<Long, Integer> idx = new HashMap<>();
        for (int i = 0; i < V0.size(); ++i) {
            idx.put(V0.get(i), i);
        }

        int[][] Vidx = new int[lP + 1][];
        for (int i = 0; i <= lP; ++i) {
            ArrayList<Long> vec = V[i];
            int[] idv = new int[vec.size()];
            for (int pos = 0; pos < vec.size(); pos++) {
                idv[pos] = idx.get(vec.get(pos));
            }
            Vidx[i] = idv;
        }

        int total = 0;
        int[] Svals = new int[V0.size()];

        for (int k = 1; k <= K; ++k) {
            for (int id : Vidx[0]) {
                Svals[id] = F.eval(V0.get(id), k);
            }

            for (int i = 0; i < lP; ++i) {
                long p = P.get(i);
                long p2 = p * p;
                int pk = modPow(p % MOD, k);
                int t = mulMod(pk, subMod(pk, 1));

                ArrayList<Long> vec = V[i + 1];
                int[] idv = Vidx[i + 1];

                for (int pos = 0; pos < vec.size(); ++pos) {
                    long x = vec.get(pos);
                    if (x < p2)
                        break;
                    int idx_x = idv[pos];
                    int cur = Svals[idx_x];

                    long pp = p2;
                    while (pp <= x) {
                        Integer it = idx.get(x / pp);
                        if (it != null) {
                            cur = subMod(cur, mulMod(t, Svals[it]));
                        }
                        if (pp > x / p)
                            break;
                        pp *= p;
                    }
                    Svals[idx_x] = cur;
                }
            }
            total = addMod(total, Svals[idx.get(n)]);
        }
        return total;
    }

    public static String solve() {
        return Integer.toString(solveTotal(1000000000000L, 50));
    }

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