bzoj1430 小猴打架

# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 9999991;

int n;
ll ans = 1;

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n-2; ++i) ans = ans * n % mod;
    for (int i=1; i<n; ++i) ans = ans * i % mod;
    cout << ans;
    return 0;
}