Vivek initially has an empty array $a$ and some integer constant $m$.

He performs the following algorithm:  Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.  Compute the greatest common divisor of integers in $a$.  In case it equals to $1$, break  Otherwise, return to step $1$. 

Find the expected length of $a$. It can be shown that it can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q\neq 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1} \pmod{10^9+7}$.


-----Input-----

The first and only line contains a single integer $m$ ($1 \leq m \leq 100000$).


-----Output-----

Print a single integer — the expected length of the array $a$ written as $P \cdot 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\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$.

Difficulty: interview

Starter code:

Solutions:
big = 100010
def gen_mu():
    mu = [1]*big
    mu[0] = 0
    P = [True]*big
    P[0] = P[1] = False
    for i in range(2,big):
        if P[i]:
            j = i
            while j<big:
                P[j] = False
                mu[j] *= -1
                j += i
            j = i*i
            while j<big:
                mu[j] = 0
                j += i*i
    return mu

m = int(input())
mu = gen_mu()

MOD = 10**9+7
def mod_inv(x):
    return pow(x, MOD-2, MOD)

s = 1
for i in range(2,big):
    # p is probabilty that i | a random number [1,m]
    p = (m//i)*mod_inv(m)
    s += (-mu[i])*(p)*mod_inv(1-p)
print(s%MOD)

# https://codeforces.com/blog/entry/66101?#comment-501153
MOD = 10 ** 9 + 7
m = int(input())
f = [0] * (m + 1)
ans = 1
for i in range(m, 1, -1):
    p = m // i * pow(m, MOD - 2, MOD)
    f[i] = p * pow(1 - p, MOD - 2, MOD) % MOD
    for j in range(2 * i, m + 1, i):
        f[i] = (f[i] - f[j]) % MOD
    ans += f[i]
print(ans % MOD)

q = 100010


def rop():
    a = [1] * q
    a[0] = 0
    s = [True] * q
    s[0] = s[1] = False
    for i in range(2, q):
        if s[i]:
            o = i
            while o < q:
                s[o] = False
                a[o] *= -1
                o += i
            o = i ** 2
            while o < q:
                a[o] = 0
                o +=  i ** 2
    return a

d = int(input())
a = rop()


def pro(x):
    return pow(x, 10 ** 9 + 5, 10 ** 9 + 7)

f = 1
for i in range(2, q):
    z = (d // i) * pro(d)
    f += (-a[i]) * z * pro(1 - z)
print(f % (10 ** 9 + 7))

'''
https://codeforces.com/contest/1139/problem/D
https://codeforces.com/blog/entry/66101?#comment-500999
https://brilliant.org/wiki/linearity-of-expectation/
https://en.wikipedia.org/wiki/Negative_binomial_distribution
Suppose there is a sequence of independent Bernoulli trials. Thus, each trial has two potential outcomes called "success" and "failure". In each trial the probability of success is p and of failure is (1 − p). We are observing this sequence until a predefined number r of failures has occurred. Then the random number of successes we have seen, X, will have the negative binomial (or Pascal) distribution:

{\displaystyle X\sim \operatorname {NB} (r,p)} {\displaystyle X\sim \operatorname {NB} (r,p)}
1. mobius function: 
2. Negative binomial distribution
'''

N = 100010

def gen_mobius_function():
    mu = [1] * N
    mu[0] = 0
    P = [True] * N
    P[0] = P[1] = False
    for i in range(2, N):
        if P[i]:
            j = i
            while j < N:
                P[j] = False
                mu[j] *= -1
                j += i
            j = i * i
            while j < N:
                mu[j] = 0
                j += i * i
    return mu

m = int(input())
mu = gen_mobius_function()

MOD = 10**9 + 7

def mod_inv(x):
    return pow(x, MOD - 2, MOD)

E = 1
for i in range(2, N):
    p = m // i * mod_inv(m)
    E += -mu[i] * p * mod_inv(1 - p) #mobius, Negative binomial function
print(E % MOD)


from math import floor
from functools import reduce
MOD = floor(1e9+7)
expected_len = [0, 1]

n = int(input())

factors = [[] for i in range(n+1)]
prime_factors = [[] for i in range(n+1)]

def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    x, y, q = ext_euclid(b, a % b)
    x, y = y, (x - (a//b) * y)
    return x, y, q


def inverse(num):
    return ext_euclid(MOD, num)[1] % MOD


inv = [0] * (n+1)
for i in range(n+1):
    inv[i] = inverse(i)

for i in range(1, n+1):
    prime_fact = False
    if len(prime_factors[i]) < 2:
        prime_factors[i].append(i)
        prime_fact = True
    
    factors[i].append(i)
    for j in range(2*i, n+ 1, i):
        factors[j].append(i)
        if prime_fact:
            prime_factors[j].append(i)

# Calculate the number i = x * y
# Such that j in [1, n // x]  gcd(j, y) == 1

def f(x, y):
    remain = 0
    new_n = n // x

    new_y = reduce(lambda x, y: x*y, prime_factors[y])
    for fact in factors[new_y]:
        if fact != 1:
            if len(prime_factors[fact]) & 1:
                remain -= new_n // fact
            else:
                remain += new_n // fact
    return new_n - remain


for i in range(2, n+1):
    # i = y * b
    e_len = 0
    for ele in factors[i]:
        if ele != i:
            e_len += (f(ele, i // ele) * expected_len[ele] * inv[n]) % MOD
    e_len = ((e_len + 1)* n *  inv[n-f(i, 1)]) % MOD
    expected_len.append(e_len)

print((sum(expected_len) * inv[n]) % MOD)


"""
    Author : thekushalghosh
    Team   : CodeDiggers
"""
import sys,math
input = sys.stdin.readline
 
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().split()))
################################################################
############ ---- THE ACTUAL CODE STARTS BELOW ---- ############
t = 1
for tt in range(t):
    m = int(input())
    q = [0] * (m + 1)
    c = 1
    for i in range(m, 1, -1):
        w = m // i * pow(m, 1000000007 - 2, 1000000007)
        q[i] = w * pow(1 - w, 1000000007 - 2, 1000000007) % 1000000007
        for j in range(2 * i, m + 1, i):
            q[i] = (q[i] - q[j]) % 1000000007
        c = c + q[i]
    print(c % 1000000007)

from sys import *
m = int(input())
q = [0] * (m + 1)
c = 1
for i in range(m, 1, -1):
    w = m // i * pow(m, 1000000007 - 2, 1000000007)
    q[i] = w * pow(1 - w, 1000000007 - 2, 1000000007) % 1000000007
    for j in range(2 * i, m + 1, i):
        q[i] = (q[i] - q[j]) % 1000000007
    c = c + q[i]
print(c % 1000000007)