import java.util.Arrays;

public class Euler537 {
    static final long MOD = 1004535809L;
    static final long PRIMITIVE_ROOT = 3L;

    static long modPow(long a, long e) {
        long r = 1;
        long x = a % MOD;
        while (e > 0) {
            if ((e & 1) == 1)
                r = (r * x) % MOD;
            x = (x * x) % MOD;
            e >>= 1;
        }
        return r;
    }

    static long modInv(long a) {
        return modPow(a, MOD - 2);
    }

    static void ntt(long[] a, boolean invert) {
        int n = a.length;
        for (int i = 1, j = 0; i < n; i++) {
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1)
                j ^= bit;
            j ^= bit;
            if (i < j) {
                long temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            long wlen = modPow(PRIMITIVE_ROOT, (MOD - 1) / len);
            if (invert)
                wlen = modInv(wlen);
            int half = len / 2;
            for (int i = 0; i < n; i += len) {
                long w = 1;
                for (int j = 0; j < half; j++) {
                    long u = a[i + j];
                    long v = (w * a[i + j + half]) % MOD;

                    long x = u + v;
                    if (x >= MOD)
                        x -= MOD;
                    a[i + j] = x;

                    long y = u - v;
                    if (y < 0)
                        y += MOD;
                    a[i + j + half] = y;

                    w = (w * wlen) % MOD;
                }
            }
        }

        if (invert) {
            long invN = modInv(n);
            for (int i = 0; i < n; i++) {
                a[i] = (a[i] * invN) % MOD;
            }
        }
    }

    static long[] convolution(long[] a, long[] b, int maxDeg) {
        if (a.length == 0 || b.length == 0)
            return new long[0];
        int need = a.length + b.length - 1;
        need = Math.min(need, maxDeg + 1);

        int nttN = 1;
        while (nttN < a.length + b.length - 1)
            nttN <<= 1;

        long[] fa = Arrays.copyOf(a, nttN);
        long[] fb = Arrays.copyOf(b, nttN);

        ntt(fa, false);
        ntt(fb, false);

        for (int i = 0; i < nttN; i++) {
            fa[i] = (fa[i] * fb[i]) % MOD;
        }

        ntt(fa, true);

        return Arrays.copyOf(fa, need);
    }

    static long[] polyPow(long[] base, int exp, int maxDeg) {
        long[] res = new long[] { 1 };
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = convolution(res, base, maxDeg);
            }
            exp >>= 1;
            if (exp > 0) {
                base = convolution(base, base, maxDeg);
            }
        }
        if (res.length < maxDeg + 1) {
            res = Arrays.copyOf(res, maxDeg + 1);
        }
        return res;
    }

    static int[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i <= n; i++)
            if (isPrime[i])
                count++;
        int[] primes = new int[count];
        for (int i = 2, idx = 0; i <= n; i++) {
            if (isPrime[i])
                primes[idx++] = i;
        }
        return primes;
    }

    static long[] buildA(int maxN) {
        int needPrimes = maxN + 1;
        int limit = 300000;
        int[] primes;
        while (true) {
            primes = sievePrimes(limit);
            if (primes.length >= needPrimes)
                break;
            limit *= 2;
        }

        long[] a = new long[maxN + 1];
        a[0] = 1;
        for (int n = 1; n <= maxN; n++) {
            a[n] = primes[n] - primes[n - 1];
        }
        return a;
    }

    static long solveT(long[] aFull, int n, int k) {
        long[] a = Arrays.copyOf(aFull, n + 1);
        long[] pk = polyPow(a, k, n);
        return pk[n];
    }

    public static String solve() {
        int N = 20000;
        int K = 20000;
        long[] aFull = buildA(N);
        long ans = solveT(aFull, N, K);
        return Long.toString(ans);
    }

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