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.*;


public class Main {
    private final static long mod = 1000000007;

    private static long power(long x, long y, long m) {
        long temp;
        if (y == 0)
            return 1;
        temp = power(x, y / 2, m);
        temp = (temp * temp) % m;
        if (y % 2 == 0)
            return temp;
        else
            return ((x % m) * temp) % m;
    }

    private static long power(long x, long y) {
        return power(x, y, mod);
    }

    private static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    private static int cmp(Pair p, Pair q) {
        return (int) (p.a == q.a ? p.b - q.b : q.a - p.a);
    }

    static int nextPowerOf2(int a) {
        return 1 << nextLog2(a);
    }

    static int nextLog2(int a) {
        return (a == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(a - 1));
    }

    private static long modInverse(long a, long m) {
        long m0 = m;
        long y = 0, x = 1;
        if (m == 1)
            return 0;
        while (a > 1) {
            long q = a / m;
            long t = m;
            m = a % m;
            a = t;
            t = y;
            y = x - q * y;
            x = t;
        }
        if (x < 0)
            x += m0;
        return x;
    }


    private static class Pair {
        int a;
        int b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return a == pair.a &&
                    b == pair.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }

        @Override
        public String toString() {
            return String.format("(%d,%d)", a, b);
        }
    }

    private static long dp[][][];

    private static int cc;

    private static void dfs(int i, int vis[], List<List<Pair>> graph) {
        if (vis[i] != 0) return;
        cc++;
        vis[i] = 1;
        for (Pair p : graph.get(i)) {
            if (p.b == 0) {
                dfs(p.a, vis, graph);
            }
        }
    }

    private static void dfs1(int i, int vis[], List<List<Pair>> graph) {
        if (vis[i] != 1) return;
        vis[i] = 2;
        dp[i][1][0] = cc;
        dp[i][1][1] = vis.length - 1 - cc;
        for (Pair p : graph.get(i)) {
            if (p.b == 0) {
                dfs1(p.a, vis, graph);
            }
        }
    }

    private static 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;
    }

    public static void main(String[] args) throws IOException {

        try (FastReader in = new FastReader();
             FastWriter out = new FastWriter()) {
            int t, i, j, k, n, m, l, r, x, y, z, p, q, ti, tidx;
            //for (t = in.nextInt(), tidx = 1; tidx <= t; tidx++)
            {
                //out.print(String.format("Case #%d: ", tidx));
                m = in.nextInt();
                long[] dp = new long[m + 1];
                dp[1] = 0;
                long minv = power(m, mod - 2, mod);
                for (i = 2; i <= m; i++) {
                    List<Integer> factors = factors(i);
                    int[] fv = new int[factors.size()];
                    int sz = factors.size();
                    for (j = factors.size() - 1; j >= 0; j--) {
                        int cf = factors.get(j);
                        fv[j] = (m - cf) / cf + 1;
                        for (k = j + 1; k < factors.size(); k++) {
                            int nf = factors.get(k);
                            if (nf % cf == 0) {
                                fv[j] -= fv[k];
                            }
                        }
                    }
                    for (j = factors.size() - 2; j >= 0; j--) {
                        int cf = factors.get(j);
                        dp[i] = (dp[i] + (((fv[j] * (1 + dp[cf])) % mod) * minv) % mod) % mod;
                    }
                    long val = (fv[sz - 1] * minv) % mod;
                    dp[i] += val;
                    long val2 = (1 - val + mod) % mod;
                    dp[i] = (dp[i] * power(val2, mod - 2, mod)) % mod;
                }

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

        }
    }


    static class FastReader implements Closeable {
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer st;

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

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

        double[] nextDoubleArr(int n) {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextDouble();
            }
            return arr;
        }

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

        String[] nextStrArr(int n) {
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) {
                arr[i] = next();
            }
            return arr;
        }

        int[][] nextIntArr2(int n, int m) {
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                arr[i] = nextIntArr(m);
            }
            return arr;
        }

        long[][] nextLongArr2(int n, int m) {
            long[][] arr = new long[n][m];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLongArr(m);
            }
            return arr;
        }

        @Override
        public void close() throws IOException {
            br.close();
        }
    }

    static class FastWriter implements Closeable {
        BufferedWriter bw;
        List<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>();

        FastWriter() {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        <T> void print(T obj) throws IOException {
            bw.write(obj.toString());
            bw.flush();
        }

        void println() throws IOException {
            print("\n");
        }

        <T> void println(T obj) throws IOException {
            print(obj.toString() + "\n");
        }

        <T> void printArrLn(T[] arr) throws IOException {
            for (int i = 0; i < arr.length - 1; i++) {
                print(arr[i] + " ");
            }
            println(arr[arr.length - 1]);
        }

        <T> void printArr2(T[][] arr) throws IOException {
            for (int j = 0; j < arr.length; j++) {
                for (int i = 0; i < arr[j].length - 1; i++) {
                    print(arr[j][i] + " ");
                }
                println(arr[j][arr.length - 1]);
            }
        }

        <T> void printColl(Collection<T> coll) throws IOException {
            for (T e : coll) {
                print(e + " ");
            }
            println();
        }

        void printCharN(char c, int n) throws IOException {
            for (int i = 0; i < n; i++) {
                print(c);
            }
        }

        @Override
        public void close() throws IOException {
            bw.close();
        }
    }


}