public class Euler423 {
    static final long MOD = 1000000007L;

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

    static boolean[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;
        if (n >= 0)
            isPrime[0] = false;
        if (n >= 1)
            isPrime[1] = false;

        for (int p = 2; p * p <= n; ++p) {
            if (!isPrime[p])
                continue;
            for (int q = p * p; q <= n; q += p) {
                isPrime[q] = false;
            }
        }
        return isPrime;
    }

    static int[] modularInverses(int n) {
        int[] inv = new int[n + 1];
        if (n >= 1)
            inv[1] = 1;
        for (int i = 2; i <= n; ++i) {
            inv[i] = (int) ((MOD - (MOD / i) * inv[(int) (MOD % i)] % MOD) % MOD);
        }
        return inv;
    }

    static String solveMod(int limit) {
        boolean[] isPrime = sievePrimes(limit + 1);
        int[] inv = modularInverses(limit + 2);
        long inv5 = modPow(5, MOD - 2);

        int t = 0;
        long p = 1;
        long bt = 1;
        long bt1 = 0;

        long answer = 0;

        for (int n = 1; n <= limit; ++n) {
            long cn = (6 * p) % MOD;
            answer += cn;
            if (answer >= MOD)
                answer -= MOD;

            if (n == limit)
                break;

            boolean nextIsPrime = isPrime[n + 1];

            long pNext, btNext, bt1Next;

            if (!nextIsPrime) {
                pNext = (6 * p + MOD - bt) % MOD;

                long btMinus1 = 0;
                if (t > 0) {
                    btMinus1 = (bt * ((5L * t) % MOD)) % MOD;
                    btMinus1 = (btMinus1 * inv[n - t]) % MOD;
                }

                btNext = (5 * bt + btMinus1) % MOD;
                bt1Next = (5 * bt1 + bt) % MOD;
            } else {
                pNext = (6 * p + 5 * bt1) % MOD;

                long bt2 = 0;
                if (t + 2 <= n - 1) {
                    bt2 = (bt1 * (n - t - 2)) % MOD;
                    bt2 = (bt2 * inv5) % MOD;
                    bt2 = (bt2 * inv[t + 2]) % MOD;
                }

                btNext = (5 * bt1 + bt) % MOD;
                bt1Next = (5 * bt2 + bt1) % MOD;
                t++;
            }

            p = pNext;
            bt = btNext;
            bt1 = bt1Next;
        }

        return Long.toString(answer);
    }

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