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.
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

        public class Frac {
            long a, b;
            Frac(long a, long b) {
                this.a = a % mod;
                this.b = b % mod;
            }
            Frac add(Frac other) {
                return new Frac(a * other.b + b * other.a, b * other.b);
            }
            Frac mult(Frac other) {
                return new Frac(a * other.a, b * other.b);
            }

            @Override
            public String toString() {
                return Double.toString((a + 0.0) / b);
            }

            long pow(long a, int b) {
                if (b == 0) return 1;
                if (b % 2 == 0) return pow(a * a % mod, b >> 1);
                return a * pow(a * a % mod, b >> 1) % mod;
            }

            long inv(long a) {
                return pow(a , mod - 2);
            }

            long val() {
                return a * inv(b) % mod;
            }
        }

        int mod = 1_000_000_007;
        int[] factors;
        int[] phi;
        List<Integer> primes;
        Map<Integer, Integer>[] factor;
        int m;
        public void sieve() {
            int M = 100010;
            factors = new int[M];
            phi = new int[M];
            phi[1] = 1;
            primes = new ArrayList<>();
            for (int i = 2; i < M; i++) {
                if (factors[i] == 0) {
                    factors[i] = i;
                    primes.add(i);
                    phi[i] = i - 1;
                }
                for (int j : primes) {
                    int v = j * i;
                    if (v >= M) break;
                    factors[v] = j;
                    if (i % j == 0) {
                        phi[v] = phi[i] * j;
                        break;
                    } else {
                        phi[v] = phi[i] * phi[j];
                    }
                }
            }
            factor = new Map[M];
            for (int i = 1; i < M; i++) {
                factor[i] = factorize(i);
            }
        }

        public Map<Integer, Integer> factorize(int t) {
            Map<Integer, Integer> factor = new HashMap<>();
            while (t != 1) {
                int f = factors[t];
                int cnt = 0;
                while (t % f == 0) {
                    t /= f;
                    cnt ++;
                }
                factor.put(f, cnt);
            }
            return factor;
        }

        void fr(Map<Integer, Integer> visit, Map<Integer, Integer> fa, int f) {
            Map<Integer, Integer> fb = factor[f];
            List<Integer> forbidPrimes = new ArrayList<>();
            for (Map.Entry<Integer, Integer> en: fa.entrySet()) {
                if (!fb.getOrDefault(en.getKey(), -1).equals(en.getValue())) {
                    forbidPrimes.add(en.getKey());
                }
            }
            int n = forbidPrimes.size();
            int chooseFrom = m / f;
            int tot = chooseFrom;
            for (int i = 1; i < 1 << n; i++) {
                int on = 0;
                int val = 1;
                for (int j = 0; j < n; j++) {
                    if (((1 << j) & i) != 0) {
                        val *= forbidPrimes.get(j);
                        on += 1;
                    }
                }
                tot = tot + (on % 2 == 1 ? -1 : 1) * (chooseFrom / val);
            }
            visit.put(f, tot);
        }

        Frac[] dp;
        int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
        public Frac get(int y) {
            if (y == 1) return new Frac(0, 1);
            if (dp[y] != null) return dp[y];
            Map<Integer, Integer> visit = new HashMap<>();
            Map<Integer, Integer> fa = factor[y];
            for (int f = 1; f * f <= y; f++) {
                if (y % f == 0) {
                    fr(visit, fa, f);
                    if (f * f != y) {
                        fr(visit, fa, y / f);
                    }
                }
            }
            int tot = 0;
            for (Map.Entry<Integer, Integer> en: visit.entrySet()) {
                tot += en.getValue();
            }
            if (tot != m) {
                throw new RuntimeException();
            }
            Frac expect = new Frac(0, 1);
            int x = visit.get(y);
            for (Map.Entry<Integer, Integer> en: visit.entrySet()) {
                if (en.getKey() == y) {
                    continue;
                }
                Frac prob = new Frac(en.getValue(), m - x);
                expect = expect.add(prob.mult(get(en.getKey()).add(new Frac(1, 1))));
            };
            return dp[y] = expect.add(new Frac(x, m - x));
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            sieve();
            m = sc.nextInt();
            dp = new Frac[m + 1];
            Frac tot = new Frac(0, 1);
            for (int i = 1; i <= m; i++) {
                tot= tot.add(get(i).add(new Frac(1, 1)));
            }
            Frac ret = tot.mult(new Frac(1 , m));
            pw.println(ret.val());
        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}