public class Euler560 {
    static final int kMod = 1000000007;

    static int modPow(int base, int exp) {
        long result = 1;
        long b = base;
        int e = exp;
        while (e > 0) {
            if ((e & 1) != 0)
                result = (result * b) % kMod;
            b = (b * b) % kMod;
            e >>= 1;
        }
        return (int) result;
    }

    static class SieveData {
        int[] spf;
        int[] pi;

        SieveData(int limit) {
            spf = new int[limit + 1];
            pi = new int[limit + 1];
            if (limit < 2)
                return;

            int[] primes = new int[limit / 10 + 32];
            int numPrimes = 0;

            for (int i = 2; i <= limit; i++) {
                if (spf[i] == 0) {
                    spf[i] = i;
                    if (numPrimes < primes.length) {
                        primes[numPrimes++] = i;
                    } else {
                        int[] newPrimes = new int[primes.length * 2];
                        System.arraycopy(primes, 0, newPrimes, 0, numPrimes);
                        primes = newPrimes;
                        primes[numPrimes++] = i;
                    }
                }

                for (int j = 0; j < numPrimes; j++) {
                    int p = primes[j];
                    long v = (long) i * p;
                    if (v > limit)
                        break;
                    spf[(int) v] = p;
                    if (p == spf[i])
                        break;
                }
            }

            int primeCount = 0;
            for (int x = 1; x <= limit; x++) {
                if (x >= 2 && spf[x] == x) {
                    primeCount++;
                }
                pi[x] = primeCount;
            }
        }
    }

    static void fwhtXor(int[] a) {
        int n = a.length;
        for (int len = 1; len < n; len <<= 1) {
            int step = len << 1;
            for (int i = 0; i < n; i += step) {
                for (int j = 0; j < len; j++) {
                    int u = a[i + j];
                    int v = a[i + j + len];
                    a[i + j] = (u + v >= kMod) ? (u + v - kMod) : (u + v);
                    a[i + j + len] = (u >= v) ? (u - v) : (u + kMod - v);
                }
            }
        }
    }

    static int solveLosingPositions(int n, int k) {
        int limit = n - 1;
        SieveData sieve = new SieveData(limit);

        int maxIndex = Math.max(1, sieve.pi[limit]);
        int[] counts = new int[maxIndex + 1];

        counts[0] = limit / 2;
        counts[1] = 1;

        for (int x = 3; x <= limit; x += 2) {
            int p = sieve.spf[x];
            int idx = sieve.pi[p];
            counts[idx]++;
        }

        int size = 1;
        while (size < counts.length) {
            size <<= 1;
        }

        int[] transformed = new int[size];
        for (int i = 0; i < counts.length; i++) {
            transformed[i] = counts[i] % kMod;
        }

        fwhtXor(transformed);

        for (int i = 0; i < size; i++) {
            transformed[i] = modPow(transformed[i], k);
        }

        fwhtXor(transformed);

        int invSize = modPow(size % kMod, kMod - 2);
        long answer = ((long) transformed[0] * invSize) % kMod;
        return (int) answer;
    }

    public static String solve() {
        return Integer.toString(solveLosingPositions(10000000, 10000000));
    }

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