import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Euler956 {

    static final long K_MOD = 999999001L;

    static long modPow(long base, long exp, long mod) {
        long result = 1L % mod;
        long cur = base % mod;
        while (exp > 0) {
            if ((exp & 1L) != 0L) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            exp >>= 1L;
        }
        return result;
    }

    static long modInv(long x, long mod) {
        return modPow(x, mod - 2L, mod);
    }

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>(n / 5);

        for (int i = 2; i <= n; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long v = (long) i * p;
                if (v > n || p > spf[i]) {
                    break;
                }
                spf[(int) v] = p;
            }
        }
        return spf;
    }

    static class Factor {
        int p;
        long e;

        Factor(int p, long e) {
            this.p = p;
            this.e = e;
        }
    }

    static List<Factor> primeExponentsSuperduper(int n) {
        int[] spf = buildSpf(n);
        long[] exp = new long[n + 1];

        for (int t = 1; t <= n; ++t) {
            long coef = (long) (n - t + 1) * (n - t + 2) / 2L;
            int x = t;
            while (x > 1) {
                int p = spf[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    ++cnt;
                }
                exp[p] += coef * cnt;
            }
        }

        List<Factor> factors = new ArrayList<>();
        for (int p = 2; p <= n; ++p) {
            if (exp[p] != 0L) {
                factors.add(new Factor(p, exp[p]));
            }
        }
        return factors;
    }

    static long dMod(int n, int m, long mod) {
        List<Factor> factors = primeExponentsSuperduper(n);
        long[] dp = new long[m];
        long[] next = new long[m];
        long[] coeff = new long[m];
        dp[0] = 1L;

        for (Factor f : factors) {
            long p = f.p;
            long e = f.e;
            long q = modPow(p, m, mod);

            long pPowT = 1L;
            for (int t = 0; t < m; ++t) {
                if (e >= t) {
                    long cnt = (e - t) / m + 1L;
                    long geom;
                    if (q == 1L) {
                        geom = cnt % mod;
                    } else {
                        long num = (modPow(q, cnt, mod) + mod - 1L) % mod;
                        long denInv = modInv((q + mod - 1L) % mod, mod);
                        geom = (num * denInv) % mod;
                    }
                    coeff[t] = (pPowT * geom) % mod;
                } else {
                    coeff[t] = 0L;
                }
                pPowT = (pPowT * p) % mod;
            }

            Arrays.fill(next, 0L);
            for (int r = 0; r < m; ++r) {
                if (dp[r] == 0L)
                    continue;
                long base = dp[r];
                for (int t = 0; t < m; ++t) {
                    int idx = (r + t >= m) ? (r + t - m) : (r + t);
                    next[idx] = (next[idx] + (base * coeff[t]) % mod) % mod;
                }
            }
            System.arraycopy(next, 0, dp, 0, m);
        }

        return dp[0];
    }

    public static String solve() {
        return Long.toString(dMod(1000, 1000, K_MOD));
    }

    public static void main(String[] args) {
        BigInteger exact = new BigInteger("6368195719791280");
        long sampleMod = dMod(6, 6, K_MOD);
        if (sampleMod != exact.mod(BigInteger.valueOf(K_MOD)).longValue()) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}