#include using namespace std; using ll = long long int; ll dp[5010][5010], cnt[5010], MOD = 1000000007; int main() { int N; cin >> N; dp[0][0] = 1; for(int i=0; i> val; cnt[val]++; } for(int i=0; i=0; i--) { ll val = dp[N][i] * fact % MOD; if(i % 2 == 0) ans = (ans + val ) % MOD; else ans = (ans - val + MOD) % MOD; (fact *= (++cnt)) %= MOD; } cout << ans << endl; return 0; }