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.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.BitSet;
import java.io.InputStream;

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

    static class DStepsToOne {
        NumberTheory.Mod107 mod = new NumberTheory.Mod107();

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

            int[] mu = LinearSieve.sieve(m, LinearSieve.mobius);
            for (int i = 0; i < mu.length; i++) {
                if (mu[i] == -1)
                    mu[i] = (int) (mod.modulus() - 1);
            }

            long answer = 1;
            for (int i = 2; i <= m; i++) {
                if (mu[i] == 0)
                    continue;
                long sign = mod.negative(mu[i]);
                long r = mod.div(m / i, m);
                long term = mod.mult(sign, r, mod.inv(mod.subtract(1, r)));
                answer = mod.add(answer, term);
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public final BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class NumberTheory {
        private static void ASSERT(boolean assertion) {
            if (!assertion)
                throw new AssertionError();
        }

        public abstract static class Modulus<M extends NumberTheory.Modulus<M>> {
            final ArrayList<Long> factorial = new ArrayList<>();
            final ArrayList<Long> invFactorial = new ArrayList<>();

            public abstract long modulus();

            public Modulus() {
                super();
                factorial.add(1L);
                invFactorial.add(1L);
            }

            public long normalize(long x) {
                x %= modulus();
                if (x < 0)
                    x += modulus();
                return x;
            }

            public long add(long a, long b) {
                long v = a + b;
                return v < modulus() ? v : v - modulus();
            }

            public long subtract(long a, long b) {
                long v = a - b;
                return v < 0 ? v + modulus() : v;
            }

            public long mult(long... x) {
                long r = 1;
                for (long i : x)
                    r = mult(r, i);
                return r;
            }

            public long mult(long a, long b) {
                return (a * b) % modulus();
            }

            public long div(long a, long b) {
                return mult(a, inv(b));
            }

            public long negative(long x) {
                return x == 0 ? 0 : modulus() - x;
            }

            public long inv(long value) {
                long g = modulus(), x = 0, y = 1;
                for (long r = value; r != 0; ) {
                    long q = g / r;
                    g %= r;

                    long temp = g;
                    g = r;
                    r = temp;

                    x -= q * y;

                    temp = x;
                    x = y;
                    y = temp;
                }

                ASSERT(g == 1);
                ASSERT(y == modulus() || y == -modulus());

                return normalize(x);
            }

        }

        public static class Mod107 extends NumberTheory.Modulus<NumberTheory.Mod107> {
            public long modulus() {
                return 1_000_000_007L;
            }

        }

    }

    static class LinearSieve {
        public final BitSet isComposite;
        public final int[] leastPrimeDivisor;
        public final int[] primes;
        public static final LinearSieve.PrimePowerFunction mobius = (p, k) -> (k == 0 ? 1 : 0) - (k == 1 ? 1 : 0);

        public LinearSieve(int n) {
            double estimate;
            if (n < 10000) {
                estimate = n + 1;
            } else {
                estimate = ((double) n) / Math.log(n);
                estimate *= 1.1;
            }
            int[] primes = new int[(int) estimate];
            leastPrimeDivisor = new int[n + 1];
            int size = 0;

            if (n <= 1) {
                isComposite = new BitSet();
            } else {
                isComposite = new BitSet(n + 1);

                for (int i = 2; i <= n; i++) {
                    if (!isComposite.get(i)) {
                        if (size >= primes.length)
                            primes = resize(primes);
                        primes[size++] = i;
                        leastPrimeDivisor[i] = i;
                    }

                    for (int j = 0; j < size; j++) {
                        int p = primes[j];
                        if (i * p > n)
                            break;
                        isComposite.set(i * p);
                        leastPrimeDivisor[i * p] = p;
                        if (i % p == 0)
                            break;
                    }
                }
            }

            this.primes = new int[size];
            System.arraycopy(primes, 0, this.primes, 0, size);
        }

        private static int[] resize(int[] primes) {
            int newSize = 1 + ((primes.length * 11) / 10);
            int[] newPrimes = new int[newSize];
            System.arraycopy(primes, 0, newPrimes, 0, primes.length);
            return newPrimes;
        }

        public static int[] sieve(int n, LinearSieve.PrimePowerFunction function) {
            ASSERT(n >= 1);

            BitSet isComposite = new BitSet();
            int[] f = new int[n + 1];
            int[] count = new int[n + 1];
            List<Integer> primes = new ArrayList<>();

            f[1] = 1;

            for (int i = 2; i <= n; i++) {
                if (!isComposite.get(i)) {
                    primes.add(i);
                    f[i] = function.forPrimePower(i, 1);
                    count[i] = 1;
                }

                for (int p : primes) {
                    if (i * p > n)
                        break;

                    isComposite.set(i * p);

                    if (i % p == 0) {
                        f[i * p] = f[i] * function.forPrimePower(p, count[i] + 1);
                        int div = function.forPrimePower(p, count[i]);
                        if (div != 0)
                            f[i * p] /= div;
                        else
                            ASSERT(f[i * p] == 0);
                        count[i * p] = count[i] + 1;
                    } else {
                        f[i * p] = f[i] * f[p];
                        count[i * p] = 1;
                    }
                }
            }

            return f;
        }

        private static void ASSERT(boolean assertion) {
            if (!assertion)
                throw new AssertionError();
        }

        interface PrimePowerFunction {
            int forPrimePower(int p, int k);

        }

    }
}

