public class Euler840 {
    static final int kMod = 999676999;

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        for (int i = 0; i <= n; ++i)
            spf[i] = i;
        for (int i = 2; (long) i * i <= n; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j)
                        spf[j] = i;
                }
            }
        }
        return spf;
    }

    static int[] buildDMod(int n, int[] spf) {
        int[] d = new int[n + 1];
        d[1] = 1;
        for (int x = 2; x <= n; ++x) {
            if (spf[x] == x) {
                d[x] = 1;
            } else {
                int p = spf[x];
                int q = x / p;
                d[x] = (int) (((long) p * d[q] + q) % kMod);
            }
        }
        return d;
    }

    static int[] buildGMod(int n, int[] d) {
        int[] g = new int[n + 1];
        g[0] = 1;
        for (int part = 1; part <= n; ++part) {
            int w = d[part];
            if (w == 1) {
                for (int s = part; s <= n; ++s) {
                    int v = g[s] + g[s - part];
                    if (v >= kMod)
                        v -= kMod;
                    g[s] = v;
                }
            } else {
                for (int s = part; s <= n; ++s) {
                    g[s] = (int) ((g[s] + (long) w * g[s - part]) % kMod);
                }
            }
        }
        return g;
    }

    public static String solve() {
        int n = 50000;
        int[] spf = buildSpf(n);
        int[] d = buildDMod(n, spf);
        int[] g = buildGMod(n, d);

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += g[i];
            if (ans >= kMod)
                ans -= kMod;
        }

        return Integer.toString(ans);
    }

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