全てのiに対して1<=a[i]<=nを満たす長さnの数列が与えられます。
iからa[i]に対して有向辺を張ったグラフを考えます。
このようなグラフはn^n通り存在しますが
そのようなグラフに含まれる単純なサイクルの数の合計を答えろ
※単純なサイクルの意味は雰囲気で察して下さい
制約
1<=n<=10^6
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
mint ans = 0;
rep2(i, 1, n + 1) {
mint sub = c(n, i);
sub *= pow_mod(n - i, n - i, mod);
sub *= c.fact[i - 1];
ans += sub;
}
cout << ans.val() << endl;
}O(1)で出来ないかなと思ったけど
