C++ 解法, 执行用时: 28ms, 内存消耗: 720K, 提交时间: 2022-04-07 21:23:28

#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <bitset>
#include <cstring>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ull unsigned long long
int n,k,dp[100005];
const int mod=1e9+7;
int qkpow(int a,int b){
	int base=a,ans=1;
	while(b){
		if(b&1)ans=1ll*ans*base%mod;
		base=1ll*base*base%mod;
		b>>=1; 
	}
	return ans;
}
int main() {
	scanf("%d %d",&n,&k);
	dp[0]=0,dp[1]=qkpow(2,n)-1,dp[2]=1ll*(dp[1]-1)*n%mod*qkpow(n-1,mod-2)%mod;
	for(int i=2;i<k;i++){
		dp[i+1]=1ll*n*(dp[i]-(1ll*dp[i-1]*i%mod*qkpow(n,mod-2)%mod)-1)%mod*qkpow(n-i,mod-2)%mod;
	}
	printf("%d\n",(dp[k]+mod)%mod);
    return 0;
}
/*
dp[i]=k[i]dp[i+1]
dp[i]-dp[i-1]*(n-i+1)/n=dp[i+1]*(i+1)/n+1
dp[i]=k[i-1]dp[i](n-i+1)/n+dp[i+1]*(i+1)/n
*/