#include using namespace std; using ll = long long; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> N >> K; prepare_nCr(); ll left = N*(N+1)/2 % mod * nPk(N-1, K) % mod; ll right = N*(N-1)/2 % mod * nCr(N-2, K-2) % mod * Per[K] % mod * mod_pow(2, 1000000005) % mod; ll ans = left + right; ans %= mod; p(ans); return 0; }