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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;

public final class CF_548_D2_D
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static int pgcd(int a,int b){
		if (a<b)
			return pgcd(b,a);
		while (b!=0){
			int c=b;
			b=a%b;
			a=c;
		}
		return a;
	}

	static long powerMod(long b,long e,long m){
		long x=1;
		while (e>0) {
			if (e%2==1)
				x=(b*x)%m;
			b=(b*b)%m;
			e=e/2;
		}
		return x; 
	}

	static long mod=1000000007;

	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static int coprimes(int x,int max,ArrayList<Integer>[] div,int[] mu){
		int res=0;
		for (int d:div[x]){

			int bob=max/d;
			res+=mu[d]*bob;
		}

		/*
		int zn=0;
		for (int u=1;u<=max;u++){
			if (pgcd(u,x)==1)
				zn++;
		}

		if (zn!=res){
			log("error: x"+x+" zn:"+zn+" res:"+res);
		}
		 */
		return res;
	}

	static void process() throws Exception {

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);
		//test();
		int m=reader.readInt();
		int MX=m+1;


		int[] mem=new int[MX];
		int[] cnt=new int[MX];

		ArrayList<Integer> primes=new ArrayList<Integer>();

		int[] mu=new int[MX];
		Arrays.fill(mu,1);
		for (int u=2;u<MX;u++){
			if (mem[u]==0){
				int v=u;
				primes.add(u);
				while (v<MX){
					mem[v]=u;
					mu[v]*=-1;
					if (v%(u*u)==0)
						mu[v]=0;
					v+=u;
				}
			}
		}





		ArrayList<Integer>[] div=new ArrayList[MX];

		for (int x=1;x<MX;x++){
			div[x]=new ArrayList<Integer>();
			for (int d=1;d*d<=x;d++){
				if (x%d==0){
					div[x].add(d);
					if (x!=d*d)
						div[x].add(x/d);
				}
			}

		}




		long[] ans=new long[MX];
		ans[1]=0;

		long invm=powerMod(m,mod-2,mod);
		
		long res=0;
		
		if (m>1) {
	
		
			
			for (int x=2;x<MX;x++){
				//log("=========x:"+x);
				for (int d:div[x]){
					if (d!=x){
						// how many y lead to d ?
						// x=d*e
						// y=d*f, with f coprime with e, and f in [1..(MX-1)/d]
						int fmax=m/d;
						int e=x/d;
						////log("d:"+d+" e:"+e);

						long zn=coprimes(e,fmax,div,mu);
						zn*=invm;
						if (zn>=mod)
							zn%=mod;
						////log("fmax:"+fmax+"   zn:"+zn);
						// we have zn/m chance to pick y

						long vn=(1+ans[d]);
						vn%=mod;
				
						long delta=zn*vn;
						delta%=mod;
						ans[x]+=delta;
						ans[x]%=mod;
					}
				}
				long mult=m/x;
				long probx=mult*invm;
				probx%=mod;
				//log("check:"+(probx*m)%mod);
				//log("prob:"+probx);
				long a=1+mod-probx;
				
				if (a>=mod)
					a-=mod;
				//log("x:"+x+"  a:"+a);
				ans[x]+=probx;
				if (ans[x]>=mod)
					ans[x]-=mod;
				ans[x]*=powerMod(a,mod-2,mod);
				if (ans[x]>=mod)
					ans[x]%=mod;
				
				res+=ans[x];
				if (res>=mod)
					res-=mod;
			}
			res*=invm;
			
		}
		res+=1;
		if (res>=mod)
			res%=mod;
		
		output(res);




		try {
			out.close();
		} catch (Exception e) {
		}

	}

	public static void main(String[] args) throws Exception {
		process();

	}

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

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

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}