public class Euler522 {

    static final int kMod = 135707531;
    static final int kDefaultN = 12344321;

    static int modPow(int base, int exp) {
        long res = 1;
        long cur = base % kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * cur) % kMod;
            cur = (cur * cur) % kMod;
            exp >>= 1;
        }
        return (int) res;
    }

    static int computeF(int n) {
        if (n < 2)
            return 0;

        int[] inv = new int[n + 1];
        inv[1] = 1;
        for (int i = 2; i <= n; i++) {
            inv[i] = (int) (kMod - (long) (kMod / i) * inv[kMod % i] % kMod);
        }

        int factN = 1;
        for (int i = 2; i <= n; i++) {
            factN = (int) ((long) factN * i % kMod);
        }

        int[] invfact = new int[n + 1];
        invfact[0] = 1;
        for (int i = 1; i <= n; i++) {
            invfact[i] = (int) ((long) invfact[i - 1] * inv[i] % kMod);
        }

        int termZ = (int) (((long) (n % kMod) * ((n - 1) % kMod)) % kMod);
        termZ = (int) ((long) termZ * modPow(n - 2, n - 1) % kMod);

        if (n < 4)
            return termZ;

        long sumC0 = 0;
        for (int m = 2; m < n - 1; m++) {
            long term = (long) factN * invfact[m] % kMod;
            term = term * inv[n - m] % kMod;
            term = term * modPow(m - 1, m) % kMod;
            sumC0 += term;
            if (sumC0 >= kMod)
                sumC0 -= kMod;
        }

        int total = termZ + (int) sumC0;
        if (total >= kMod)
            total -= kMod;
        return total;
    }

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