import java.util.*;

public class Euler337 {

    static final int MOD = 100000000;

    static List<Integer> sievePrimes(int limit) {
        List<Integer> primes = new ArrayList<>();
        if (limit < 2)
            return primes;
        byte[] isComposite = new byte[limit + 1];

        for (int i = 2; i <= limit; i++) {
            if (isComposite[i] == 0) {
                primes.add(i);
                if ((long) i * i <= limit) {
                    for (long j = (long) i * i; j <= limit; j += i) {
                        isComposite[(int) j] = 1;
                    }
                }
            }
        }
        return primes;
    }

    static int[] computeTotients(int n) {
        int[] phi = new int[n + 1];
        for (int i = 0; i <= n; i++)
            phi[i] = i;

        List<Integer> primes = sievePrimes(n);
        for (int p : primes) {
            for (int x = p; x <= n; x += p) {
                phi[x] -= phi[x] / p;
            }
        }
        return phi;
    }

    static class Fenwick {
        int n;
        int[] bit;

        Fenwick(int n) {
            this.n = n;
            bit = new int[n + 1];
        }

        void addPoint(int index, int delta) {
            for (int i = index; i <= n; i += i & -i) {
                int next = bit[i] + delta;
                if (next >= MOD)
                    next -= MOD;
                bit[i] = next;
            }
        }

        void rangeAdd(int left, int right, int delta) {
            if (left < 1)
                left = 1;
            if (right > n)
                right = n;
            if (left > right || delta == 0)
                return;

            addPoint(left, delta);
            if (right + 1 <= n) {
                int neg = (delta == 0) ? 0 : (MOD - delta);
                addPoint(right + 1, neg);
            }
        }

        int pointQuery(int index) {
            int out = 0;
            for (int i = index; i > 0; i -= i & -i) {
                out += bit[i];
                if (out >= MOD)
                    out -= MOD;
            }
            return out;
        }
    }

    static int countSequencesMod(int n, int[] phi) {
        if (n < 6)
            return 0;
        Fenwick fenwick = new Fenwick(n);
        int total = 1;
        fenwick.rangeAdd(phi[6] + 1, 5, 1);

        for (int x = 7; x <= n; x++) {
            int dpX = fenwick.pointQuery(phi[x]);
            total += dpX;
            if (total >= MOD)
                total -= MOD;
            fenwick.rangeAdd(phi[x] + 1, x - 1, dpX);
        }
        return total;
    }

    public static String solve() {
        int n = 20000000;
        int[] phi = computeTotients(n);
        int ans = countSequencesMod(n, phi);
        return String.valueOf(ans);
    }

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