import java.util.ArrayList;
import java.util.List;

public class Euler908 {

    static final long kMod = 1111211113L;

    static List<Integer> primesUpTo(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;
        for (int p = 2; (long) p * p <= n; ++p) {
            if (isPrime[p]) {
                for (int q = p * p; q <= n; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int x = 2; x <= n; ++x) {
            if (isPrime[x]) {
                primes.add(x);
            }
        }
        return primes;
    }

    static int[] mobiusArray(int n) {
        int[] mu = new int[n + 1];
        int[] spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>();
        mu[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                long v = 1L * i * p;
                if (v > n || p > spf[i]) {
                    break;
                }
                spf[(int) v] = p;
                if (i % p == 0) {
                    mu[(int) v] = 0;
                    break;
                }
                mu[(int) v] = -mu[i];
            }
        }
        return mu;
    }

    static class State908 {
        long integer;
        int count;
        int primeIndex;

        State908(long integer, int count, int primeIndex) {
            this.integer = integer;
            this.count = count;
            this.primeIndex = primeIndex;
        }
    }

    static List<State908> enumerateStates(int nLimit) {
        List<Integer> primes = primesUpTo(2 * nLimit);
        List<State908> states = new ArrayList<>();

        for (long x = 1; x <= 2L * nLimit; x <<= 1) {
            states.add(new State908(x, (int) x, 1));
        }

        for (int head = 0; head < states.size(); ++head) {
            State908 st = states.get(head);
            if (st.count > nLimit) {
                continue;
            }
            int maxNewValueFactor = nLimit / st.count;
            if (maxNewValueFactor < 2) {
                continue;
            }
            int maxPrime = 2 * maxNewValueFactor - 1;
            for (int newPrimeIndex = st.primeIndex; newPrimeIndex < primes.size(); ++newPrimeIndex) {
                int prime = primes.get(newPrimeIndex);
                if (prime > maxPrime) {
                    break;
                }
                long newInteger = st.integer * prime;
                long primePower = prime;
                int newValueFactor = (prime + 1) / 2;

                while (newValueFactor <= maxNewValueFactor) {
                    int newValue = st.count * newValueFactor;
                    states.add(new State908(newInteger, newValue, newPrimeIndex + 1));

                    java.math.BigInteger nextPrimePower = java.math.BigInteger.valueOf(primePower)
                            .multiply(java.math.BigInteger.valueOf(prime));
                    if (nextPrimePower.compareTo(java.math.BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
                        break;
                    }
                    primePower = nextPrimePower.longValue();

                    java.math.BigInteger numerator = java.math.BigInteger.valueOf(prime)
                            .multiply(java.math.BigInteger.valueOf(primePower));
                    long denom = 2L * prime + 2L;
                    newValueFactor = (int) (numerator.divide(java.math.BigInteger.valueOf(denom)).longValue() + 1L);

                    java.math.BigInteger nextInteger = java.math.BigInteger.valueOf(newInteger)
                            .multiply(java.math.BigInteger.valueOf(prime));
                    if (nextInteger.compareTo(java.math.BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
                        break;
                    }
                    newInteger = nextInteger.longValue();
                }
            }
        }

        return states;
    }

    static long countClockSequences(int nLimit) {
        List<State908> states = enumerateStates(nLimit);

        long[] inv = new long[nLimit + 2];
        inv[1] = 1;
        for (int i = 2; i <= nLimit + 1; ++i) {
            inv[i] = (kMod - (kMod / i) * inv[(int) (kMod % i)] % kMod) % kMod;
        }

        long[] rep = new long[nLimit + 1];

        int threads = Math.max(1, Runtime.getRuntime().availableProcessors());
        if (threads > 16)
            threads = 16;
        if (threads > states.size())
            threads = states.size();

        long[][] localRep = new long[threads][nLimit + 1];
        Thread[] pool = new Thread[threads];
        int base = states.size() / threads;
        int rem = states.size() % threads;

        int cur = 0;
        for (int i = 0; i < threads; ++i) {
            final int tIdx = i;
            final int start = cur;
            final int len = base + (i < rem ? 1 : 0);
            final int end = start + len;
            cur += len;

            pool[i] = new Thread(() -> {
                for (int idx = start; idx < end; ++idx) {
                    State908 st = states.get(idx);
                    if (st.count > nLimit)
                        continue;

                    long free = st.integer - st.count;
                    int maxK = (int) Math.min(free, (long) (nLimit - st.count));

                    long comb = 1;
                    int p = st.count;
                    for (int k = 0; k <= maxK; ++k) {
                        localRep[tIdx][p] += comb;
                        if (localRep[tIdx][p] >= kMod) {
                            localRep[tIdx][p] -= kMod;
                        }
                        if (k == maxK)
                            break;
                        comb = (comb * ((free - k) % kMod)) % kMod;
                        comb = (comb * inv[k + 1]) % kMod;
                        p++;
                    }
                }
            });
            pool[i].start();
        }

        try {
            for (int i = 0; i < threads; i++) {
                if (pool[i] != null)
                    pool[i].join();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < threads; ++i) {
            for (int p = 1; p <= nLimit; ++p) {
                rep[p] += localRep[i][p];
                if (rep[p] >= kMod) {
                    rep[p] -= kMod;
                }
            }
        }

        for (int i = 2; i <= nLimit; ++i) {
            rep[i] += rep[i - 1];
            if (rep[i] >= kMod) {
                rep[i] -= kMod;
            }
        }

        int[] mu = mobiusArray(nLimit);
        long result = 0;
        for (int i = 1; i <= nLimit; ++i) {
            result += (long) mu[i] * rep[nLimit / i];
            result %= kMod;
        }
        if (result < 0) {
            result += kMod;
        }
        return result;
    }

    public static String solve() {
        return Long.toString(countClockSequences(10000));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}