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.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Comparator;
import java.io.InputStream;
import java.util.ArrayList;

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

    static class DStepsToOne {
        int mod = 1000000007;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int m = in.nextInt();

            long[] dp = new long[m + 1];

            dp[1] = 0;

            long minv = pow(m, mod - 2, mod);

            for (int i = 2; i <= m; i++) {
                List<Integer> factors = factors(i);

                int[] fv = new int[factors.size()];


                int sz = factors.size();
                for (int j = factors.size() - 1; j >= 0; j--) {
                    int cf = factors.get(j);

                    fv[j] = (m - cf) / cf + 1;

                    for (int k = j + 1; k < factors.size(); k++) {
                        int nf = factors.get(k);

                        if (nf % cf == 0) {
                            fv[j] -= fv[k];
                        }
                    }
                }

                for (int j = factors.size() - 2; j >= 0; j--) {
                    int cf = factors.get(j);

                    long val = fv[j] * (1 + dp[cf]);
                    val %= mod;
                    val *= minv;
                    val %= mod;

                    dp[i] += val;
                    dp[i] %= mod;
                }

                long val = fv[sz - 1] * minv;
                val %= mod;

                dp[i] += val;

                long val2 = 1;

                val2 -= (val);

                val2 %= mod;

                dp[i] *= pow(val2, mod - 2, mod);

                dp[i] %= mod;
            }

            long ans = 0;

            for (int i = 1; i <= m; i++) {
                long val = minv * (1 + dp[i]);

                val %= mod;

                ans += val;

                ans %= mod;
            }

            if (ans < 0) {
                ans += mod;
            }

            out.println(ans);
        }

        long pow(long a, long p, int mod) {
            if (p == 0) {
                return 1;
            }

            long t = pow(a, p / 2, mod);

            if (p % 2 != 0) {
                return (((t * t) % mod) * a) % mod;
            } else {
                return (t * t) % mod;
            }
        }

        List<Integer> factors(int n) {
            List<Integer> factors = new ArrayList<>();

            for (int i = 1; i * i <= n; i++) {
                if (n % i == 0) {
                    factors.add(i);
                    if (i != n / i)
                        factors.add(n / i);
                }
            }

            factors.sort(Comparator.naturalOrder());

            return factors;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }
}

