Vivek initially has an empty array a and some integer constant m.

He performs the following algorithm:

  1. Select a random integer x uniformly in range from 1 to m and append it to the end of a. 
  2. Compute the greatest common divisor of integers in a. 
  3. In case it equals to 1, break 
  4. Otherwise, return to step 1. 



Find the expected length of a. It can be shown that it can be represented as P/Q where P and Q are coprime integers and Q≠ 0 \pmod{10^9+7}. Print the value of P ⋅ Q^{-1} \pmod{10^9+7}.

Input

The first and only line contains a single integer m (1 ≤ m ≤ 100000).

Output

Print a single integer — the expected length of the array a written as P ⋅ Q^{-1} \pmod{10^9+7}.

Examples

Input


1


Output


1


Input


2


Output


2


Input


4


Output


333333338

Note

In the first example, since Vivek can choose only integers from 1 to 1, he will have a=[1] after the first append operation, and after that quit the algorithm. Hence the length of a is always 1, so its expected value is 1 as well.

In the second example, Vivek each time will append either 1 or 2, so after finishing the algorithm he will end up having some number of 2's (possibly zero), and a single 1 in the end. The expected length of the list is 1⋅ 1/2 + 2⋅ (1)/(2^2) + 3⋅ (1)/(2^3) + … = 2.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DStepsToOne solver = new DStepsToOne();
        solver.solve(1, in, out);
        out.close();
    }

    static class DStepsToOne {
        long mod = (long) (1e9 + 7);
        int m;
        int[] LPF;
        long modinv;

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            m = in.scanInt();
            modinv = CodeX.modinv(m, mod);
            long dp[] = new long[m + 1];
            ArrayList<Integer> fac[] = new ArrayList[m + 1];
            for (int i = 0; i <= m; i++) fac[i] = new ArrayList<>();

            for (int i = 2; i <= m; i++) {
                for (int j = i; j <= m; j += i) {
                    fac[j].add(i);
                }
            }


            LPF = CodeX.SPF(m + 5);


            dp[1] = 0;

            for (int i = 2; i <= m; i++) {
                long tr = 1;
                long c = 0;


                for (int j : fac[i]) {
                    if (j == i) {
                        c += fidCount(i, j);
                    } else {
                        tr = (tr + (((dp[j] * fidCount(i, j)) % mod) * modinv) % mod) % mod;
                    }
                }

                dp[i] = (((tr * m) % mod) * CodeX.modinv(m - c, mod)) % mod;

            }
            long ans = 1;
            for (int i = 1; i <= m; i++) ans = (ans + (dp[i] * modinv) % mod) % mod;
            out.println(ans);
        }

        long fidCount(long x, long y) {
            long a = x / y;
            long currCnt = m / y;
            HashSet<Integer> hashSet = new HashSet<>();
            while (a != 1) {
                hashSet.add(LPF[(int) a]);
                a /= LPF[(int) a];
            }

            long sz = hashSet.size();
            long arr[] = new long[(int) sz];
            int l = 0;
            for (int k : hashSet) {
                arr[l++] = k;
            }
            long lim = m / y;
            for (long i = 1; i < (1 << sz); i++) {
                long sign = 1;
                long prod = 1;
                for (long j = 0; j < sz; j++) {
                    if ((i & (1 << j)) != 0) {
                        prod *= arr[(int) j];
                        sign *= -1;
                    }
                }
                currCnt += sign * (lim / prod);
            }


            return currCnt;

        }

    }

    static class CodeX {
        public static long power(long x, long y, long p) {
            long res = 1;
            x = x % p;
            while (y > 0) {
                if ((y & 1) != 0)
                    res = (res * x) % p;
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }

        public static long modinv(long k, long mod) {
            return power(k, mod - 2, mod);
        }

        public static int[] SPF(int MAXN) {
            int[] spf = new int[MAXN + 5];
            spf[1] = 1;
            for (int i = 2; i < MAXN; i++) spf[i] = i;
            for (int i = 4; i < MAXN; i += 2) spf[i] = 2;
            for (int i = 3; i * i < MAXN; i++) {
                if (spf[i] == i) {
                    for (int j = i * i; j < MAXN; j += i)
                        if (spf[j] == j)
                            spf[j] = i;
                }
            }
            return spf;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

