import java.util.*;

public class Euler344 {

    static final long MOD = 1000036000099L;
    static final long P1 = 1000003L;
    static final long P2 = 1000033L;

    static class SmallComb {
        long[][] c;

        SmallComb(int maxN) {
            c = new long[maxN + 1][maxN + 1];
            for (int n = 0; n <= maxN; n++) {
                c[n][0] = c[n][n] = 1;
                for (int k = 1; k < n; k++) {
                    c[n][k] = c[n - 1][k - 1] + c[n - 1][k];
                }
            }
        }
    }

    static long modPow(long base, long exp, long mod) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1)
                result = mulMod(result, base, mod);
            base = mulMod(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    static long mulMod(long a, long b, long mod) {
        return (long) ((((java.math.BigInteger.valueOf(a)).multiply(java.math.BigInteger.valueOf(b)))
                .remainder(java.math.BigInteger.valueOf(mod))).longValue());
    }

    static long modInvPrime(long a, long p) {
        return modPow(a, p - 2, p);
    }

    static class FactTable {
        long[] fact;
        long[] invfact;

        FactTable(int n, long p) {
            fact = new long[n + 1];
            invfact = new long[n + 1];
            fact[0] = 1;
            for (int i = 1; i <= n; i++) {
                fact[i] = (fact[i - 1] * i) % p;
            }
            invfact[n] = modInvPrime(fact[n], p);
            for (int i = n; i >= 1; i--) {
                invfact[i - 1] = (invfact[i] * i) % p;
            }
        }
    }

    static long binomModPrime(int n, int k, FactTable ft, long p) {
        if (k < 0 || k > n)
            return 0;
        long res = (ft.fact[n] * ft.invfact[k]) % p;
        res = (res * ft.invfact[n - k]) % p;
        return res;
    }

    static long crt(long a, long b) {
        long t = (b + P2 - (a % P2)) % P2;
        long inv = modInvPrime(P1 % P2, P2);
        long k = (t * inv) % P2;
        return a + P1 * k;
    }

    static long binomModComposite(int n, int k, FactTable f1, FactTable f2) {
        long a = binomModPrime(n, k, f1, P1);
        long b = binomModPrime(n, k, f2, P2);
        return crt(a, b);
    }

    static class WaysEvenMod {
        int max_s;
        long[] ways;

        WaysEvenMod(int k, int r, SmallComb comb) {
            max_s = k + r;
            ways = new long[max_s + 1];
            for (int x = 0; x <= k; x += 2) {
                long cx = comb.c[k][x];
                for (int y = 0; y <= r; y++) {
                    int s = x + y;
                    long add = mulMod(cx, comb.c[r][y], MOD);
                    ways[s] = (ways[s] + add) % MOD;
                }
            }
        }
    }

    static int bitLength(long v) {
        int bits = 0;
        while (v > 0) {
            bits++;
            v >>= 1;
        }
        return bits == 0 ? 1 : bits;
    }

    static long countWithWaysMod(long S, WaysEvenMod ways) {
        int max_s = ways.max_s;
        long[] dp = new long[max_s + 1];
        long[] next = new long[max_s + 1];
        dp[0] = 1;

        int bits = bitLength(S) + 7;
        for (int b = 0; b < bits; b++) {
            int bit = (int) ((S >> b) & 1L);
            Arrays.fill(next, 0);
            for (int carry = 0; carry <= max_s; carry++) {
                long base = dp[carry];
                if (base == 0)
                    continue;
                for (int s = 0; s <= max_s; s++) {
                    long ways_s = ways.ways[s];
                    if (ways_s == 0)
                        continue;
                    int total = s + carry;
                    if ((total & 1) != bit)
                        continue;
                    int carryOut = total >> 1;
                    long add = mulMod(base, ways_s, MOD);
                    next[carryOut] = (next[carryOut] + add) % MOD;
                }
            }
            long[] temp = dp;
            dp = next;
            next = temp;
        }
        return dp[0];
    }

    static long computeWMod(int n, int c, SmallComb comb, FactTable f1, FactTable f2) {
        int m = c + 1;
        long N = n - m;
        long total = mulMod(m, binomModComposite(n, m, f1, f2), MOD);
        if (m == 1)
            return total;

        int k = (m + 1) / 2;
        int r = m - k + 1;
        if (m % 2 == 0) {
            WaysEvenMod ways = new WaysEvenMod(k, r, comb);
            long losing = mulMod(m - 1, countWithWaysMod(N, ways), MOD);
            return (total + MOD - losing) % MOD;
        }

        WaysEvenMod ways_k = new WaysEvenMod(k, r, comb);
        WaysEvenMod ways_km1 = new WaysEvenMod(k - 1, r, comb);

        long L0 = countWithWaysMod(N, ways_k);
        long L1 = countWithWaysMod(N + 1, ways_k);
        long L1_sub = countWithWaysMod(N + 1, ways_km1);
        L1 = (L1 + MOD - L1_sub) % MOD;

        long losing = (L0 + mulMod(m - 2, L1, MOD)) % MOD;
        return (total + MOD - losing) % MOD;
    }

    public static String solve() {
        int maxSmall = 52;
        SmallComb comb = new SmallComb(maxSmall);
        int n = 1000000;
        int c = 100;
        FactTable f1 = new FactTable(n, P1);
        FactTable f2 = new FactTable(n, P2);

        long ans = computeWMod(n, c, comb, f1, f2);
        return String.valueOf(ans);
    }

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