public class Euler559 {
    static final long MOD = 1000000123L;

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

    static class Factorials {
        long[] fact;
        long[] invFact;

        Factorials(int n) {
            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) % MOD;
            }
            invFact[n] = modPow(fact[n], MOD - 2);
            for (int i = n; i >= 1; i--) {
                invFact[i - 1] = (invFact[i] * i) % MOD;
            }
        }
    }

    static long[] buildPowInvFact(long[] invFact, int n, int r) {
        long[] powInvFact = new long[n + 1];
        for (int i = 0; i <= n; i++) {
            powInvFact[i] = modPow(invFact[i], r);
        }
        return powInvFact;
    }

    static long computeCore(int n, int k, long[] powInvFact) {
        int blocks = n / k;
        int rem = n % k;

        long[] dp = new long[blocks + 1];
        dp[0] = 1;

        for (int i = 1; i <= blocks; i++) {
            long sum = 0;
            int idx = k;
            for (int j = 1; j <= i;) {
                sum += dp[i - j] * powInvFact[idx];
                j++;
                idx += k;
                if (j > i)
                    break;

                sum -= dp[i - j] * powInvFact[idx];
                j++;
                idx += k;

                if ((j & 7) == 1) {
                    sum %= MOD;
                }
            }
            sum %= MOD;
            if (sum < 0)
                sum += MOD;
            dp[i] = sum;
        }

        if (rem == 0)
            return dp[blocks];

        long total = 0;
        int idx = rem;
        for (int j = 0; j <= blocks;) {
            total += dp[blocks - j] * powInvFact[idx];
            j++;
            idx += k;
            if (j > blocks)
                break;

            total -= dp[blocks - j] * powInvFact[idx];
            j++;
            idx += k;

            if ((j & 7) == 0) {
                total %= MOD;
            }
        }
        total %= MOD;
        if (total < 0)
            total += MOD;
        return total;
    }

    static long computeQ(int n) {
        Factorials f = new Factorials(n);
        long[] powInvFact = buildPowInvFact(f.invFact, n, n);

        long total = 0;
        for (int k = 1; k <= n; k++) {
            total = (total + computeCore(n, k, powInvFact)) % MOD;
        }

        long factor = modPow(f.fact[n], n);
        return (total * factor) % MOD;
    }

    public static String solve() {
        return Long.toString(computeQ(50000));
    }

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