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.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.Function;
import java.util.function.IntBinaryOperator;
import java.util.function.IntConsumer;
import java.util.function.IntUnaryOperator;

public class MainD {

    static int M;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        M = sc.nextInt();

        System.out.println(solve());
    }

    static int MOD = 1_000_000_007;

    static int solve() {
        int m = pow(M, MOD-2);

        Osak osak = new Osak(M);

        int[] dp = new int[M+1];
        int[][] factorsCache = new int[M+1][];
        dp[1] = 1;
        for (int x = 2; x <= M; x++) {
            // 約数のどこかに落ちる
            int[] divs = osak.enumDividors(x);
            int sum = 0;
            int same = -1;
            for (int div : divs) {
                int a = x/div;
                int[] factors;
                if( factorsCache[a] != null ) {
                    factors = factorsCache[a];
                } else {
                    factors = osak.enumUniqFactors(a);
                    factorsCache[a] = factors;
                }
                int cnt = phaiEx(div, factors);

                if( div == x ) {
                    same = cnt;

                } else {
                    sum += mul(dp[div], cnt);
                    sum %= MOD;
                }
            }

            dp[x] = div(M, M-same) + div(sum, M-same);
            dp[x] %= MOD;
        }

        int ans = 0;
        for (int i = 1; i <= M; i++) {
            ans += mul(dp[i], m);
            ans %= MOD;
        }
        return ans;
    }

    static int phaiEx(int div, int[] factors) {
        return M/div - execute(factors, 1, (acc, fac) -> acc*fac, fac -> M/(fac*div));
    }

    static int execute(int[] elms, int init, IntBinaryOperator fold, IntUnaryOperator f) {
        int k = elms.length;
        // bitDPっぽいやり方で全部の組み合わせを表現できる
        int ret = 0;
        for (int b = 1; b < 1 << k; b++) {
            int x = init;
            for (int i = 0; i < k; i++) {
                if( (b & 1 << i) > 0 ) {
                    x = fold.applyAsInt(x, elms[i]);
                }
            }
            if( Integer.bitCount(b) % 2 == 1 ) {
                ret += f.applyAsInt(x);
            } else {
                ret -= f.applyAsInt(x);
            }
        }
        return ret;
    }

    static class Osak {

        static int[] mkSieve(int n) {
            int[] sieve = new int[n+1];
            sieve[0] = -1; // dont use
            sieve[1] = 1; // goal

            int root = (int)Math.sqrt(n);
            for (int i = 2; i <= root; i++) {
                if( sieve[i] == 0 ) {
                    sieve[i] = i;
                    for (int d = 2; d*i <= n; d++) {
                        sieve[i*d] = i;
                    }
                }
            }
            for (int i = root+1; i < n+1; i++) {
                if( sieve[i] == 0 ) {
                    sieve[i] = i;
                }
            }
            return sieve;
        }

        static int factorSize(int n) {
            // 6: 2 * 3 * 5 * 7 * 11 * 13 = 30030
            // 7: 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510
            // 8: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9699690
            if( n <= 2*3*5*7*11*13 ) {
                return 6;
            } else if( n <= 2*3*5*7*11*13*17 ) {
                return 7;
            } else if( n <= 2*3*5*7*11*13*17*19 ) {
                return 8;
            } else {
                return 9;
            }
        }

        int n;
        int factorSize;
        int[] sieve;

        Osak(int n) {
            this.n = n;
            this.factorSize = factorSize(n);
            this.sieve = mkSieve(n);
        }

        int[] enumUniqFactors(int x) {
            int[] fs = new int[factorSize];
            int i = -1;
            while( x != 1 ) {
                int factor = sieve[x];
                if( i == -1 || factor != fs[i] ) {
                    fs[++i] = factor;
                }
                x /= factor;
            }
            return Arrays.copyOf(fs, i+1);
        }

        int[] enumDividors(int x) {
            int[][] factors = enumFactors(x);
            int[] cnt = new int[1];
            _enumDividorsDfs(0, factors, 1, a -> cnt[0]++ );
            int[] dividors = new int[cnt[0]];
            _enumDividorsDfs(0, factors, 1, a -> dividors[--cnt[0]] = a );
            return dividors;
        }

        private void _enumDividorsDfs(int idx, int[][] factors, int x, IntConsumer c) {
            if( factors.length == idx || factors[idx] == null ) {
                c.accept(x);
                return;
            }

            int f = factors[idx][0];
            int cnt = factors[idx][1];
            for (int i = 0; i <= cnt; i++) {
                _enumDividorsDfs(idx+1, factors, x, c);
                x *= f;
            }
        }

        int[][] enumFactors(int x) {
            int[][] fs = new int[factorSize][];
            int i = -1;
            while( x != 1 ) {
                int f = sieve[x];
                if( i == -1 || fs[i][0] != f ) {
                    fs[++i] = new int[2];
                    fs[i][0] = f;
                }
                x /= f;
                fs[i][1]++;
            }
            return fs;
        }
    }

    static int div(int a, int b) {
        return mul(a, pow(b, MOD-2));
    }

    static int gcd(int a, int b) {
        while (b > 0) {
            int c = a;
            a = b;
            b = c % b;
        }
        return a;
    }

    static int pow(int base, int exp) {
        if( exp == 0 ) return 1;

        int ans = 1;
        base %= MOD;
        while( exp > 0 ) {
            if( (exp & 1) == 1 ) {
                ans = mul(ans, base);
            }

            base = mul(base, base);
            exp = exp >> 1;
        }
        return ans;
    }

    static int mul(int a, int b) {
        return (int)((long)a * b % MOD);
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

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

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static <A> void writeLines(A[] as, Function<A, String> f) {
        PrintWriter pw = new PrintWriter(System.out);
        for (A a : as) {
            pw.println(f.apply(a));
        }
        pw.flush();
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}
