一种不同的方法

#include<bits/stdc++.h>
#define int long long
#define tl 1LL
using namespace std;
const int M = 100000007;
long long fp(int a,int b){ //快速幂模板 
	long long ans = 1;
	while(b > 0) {
		if(b & 1) ans = ans * a * tl % M;
		a = a * a * tl % M;
		b >>= 1;
	}
	return ans;
}
long long f[1000005],ff[1000005],fff[1000005];
long long dp[1000005]; //dp[i] 表示前 i 个方案中可能的情况 
signed main(){
	f[1] = ff[1] = fff[1] = 1;
	long long n,m; cin >> n >> m;
	for(long long i = 2;i <= max(n,m);i++){
		f[i] = f[i - 1] * i * tl % M;
		ff[i] = (M - ff[M % i]) * (M / i) * tl % M;
		fff[i] = fff[i - 1] * ff[i] * tl % M;
	}
	dp[0] = 1;
	dp[1] = 0;
	long long po = fp(2,n) - 1,k = 1,t = po; //k：当作 A 公式使 
	for(long long i = 2;i <= m;i++){
		k = k * po * tl % M;
		po += M - 1;
		po %= M;
		/*
		转移方程：
		dp[i] = A(2^n - 1)(i - 1) - dp[i - 1] - dp[i - 2] * (i - 1) * (2^n - i + 1)
		空集不合法的数量：dp[i - 1] 
		*/
		dp[i] = (0ll + k + M - dp[i - 1] + M - dp[i - 2] * (i - 1) * tl % M * (t + M - (i - 2)) % M) * tl % M;
	}
	long long ans = dp[m] * fff[m] * tl % M;
	cout << ans;
	return 0;
}
//时间：O(N)