```c++
//排列组合、动态规划
#include <cstdio>
#include <algorithm>
#define ll long long
#define mod 100000007ll
#define maxn 1000010
using namespace std;
ll a[maxn], f[maxn], N, M, tot, inv;
ll pow(ll a, ll b)
{
ll t, ans;
for(t=a,ans=1;b;b>>=1,t=t*t%mod)if(b&1)ans=ans*t%mod;
return ans;
}
void init()
{
ll i;
scanf("%lld%lld",&N,&M);
tot=pow(2,N)-1;
a[1]=tot;
for(i=2;i<=M;i++)a[i]=a[i-1]*(tot-i+1)%mod;
for(i=1,inv=1;i<=M;i++)inv=inv*i%mod;
inv=pow(inv,mod-2)%mod;
}
void dp()
{
for(ll i=3;i<=M;i++)f[i]=(a[i-1]-f[i-1]-f[i-2]*(tot-i+2)%mod*(i-1)%mod)%mod;
}
int main()
{
init();
dp();
printf("%lld",(f[M]+mod)%mod*inv%mod);
return 0;
}
```
by ACoder_ @ 2017-03-03 15:20:06
```c++
//排列组合、动态规划
#include <cstdio>
#include <algorithm>
#define ll long long
#define mod 100000007ll
#define maxn 1000010
using namespace std;
ll a[maxn], f[maxn], N, M, tot, inv;
ll pow(ll a, ll b)
{
ll t, ans;
for(t=a,ans=1;b;b>>=1,t=t*t%mod)if(b&1)ans=ans*t%mod;
return ans;
}
void init()
{
ll i;
scanf("%lld%lld",&N,&M);
tot=pow(2,N)-1;
a[1]=tot;
for(i=2;i<=M;i++)a[i]=a[i-1]*(tot-i+1)%mod;
for(i=1,inv=1;i<=M;i++)inv=inv*i%mod;
inv=pow(inv,mod-2)%mod;
}
void dp()
{
for(ll i=3;i<=M;i++)f[i]=(a[i-1]-f[i-1]-f[i-2]*(tot-i+2)%mod*(i-1)%mod)%mod;
}
int main()
{
init();
dp();
printf("%lld",(f[M]+mod)%mod*inv%mod);
return 0;
}
```
by ACoder_ @ 2017-03-03 15:20:54
洛谷这种情况很多件
by wusiqi @ 2021-10-09 19:25:10
@[ACoder_](/user/22600) bzoj.........................
by _xyz_ @ 2023-08-17 13:16:01