这题数据量达到了1e18 所以开始考虑数学解法 对于1~k而言其实是选出一个无向无环联通图,也就是无根树,再对其随便选一个根 用Cayley公式计算为:

再乘上个k(所有节点都可为根):

而对于后半段n - k各节点就不做要求了, 所以是:

于是答案浮出水面:

因为数据量很大,所以用快速幂算法:

#include <bits/stdc++.h>
using namespace std;

long long myPow(long long mod, long long x, long long n) {
    long long res = 1;
    x %= mod;
    if (n < 0) {
        n = -n;
        x = 1 / x;
    }
    while (n) {
        if (n & 1) {
            res *= x;
            res %= mod;
        }
        x *= x;
        x %= mod;
        n >>= 1;
    }
    return res;
}

int main() {
    long long n, k, mod = 1e9 + 7;
    cin >> n >> k;
    long long ans = (myPow(mod, k, k - 1) * myPow(mod, n - k, n - k));
    ans %= mod;
    cout << ans;
    return 0;
}