题目链接：
题目要求从$S=\{1,2,3……n\}$中选出$m$个子集满足以下三个条件：
1、不能选空集
2、不能选相同的两个子集
3、每种元素出现次数必须为偶数次
我们考虑递推，设$f[i]$为选$i$个集合满足以上条件的方案数。
考虑容斥：
当确定了前$i-1$个集合后，要满足第三个条件的话，第$i$个集合是唯一确定的，所以总方案数为$A_{2^n-1}^{i-1}$。
去掉第$i$个集合是空集的情况，如果第$i$个集合是空集，那么前$i-1$个集合一定合法，即方案数为$f[i-1]$。
再去掉第$i$个集合与前面某个集合一样的情况，那么显然去掉这两个相同的集合后其他的$i-2$个集合也是合法的，第$i$个集合有$2^n-1-(i-2)$种选择，前面那个与第$i$个集合相同的集合的位置有$i-1$种选择，方案数为$(i-1)*(2^n-1-(i-2))*f[i-2]$。
至此，我们可以得到递推式子$f[i]=A_{2^n-1}^{i-1}-f[i-1]-(i-1)*(2^n-i+1)*f[i-2]$。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m;
int mod=100000007;
ll f[1000010];
ll g[1000010];
ll quick(ll x,int y)
{
ll res=1ll;
while(y)
{
if(y&1)
{
res=(res*x)%mod;
}
y/=2;
x=(x*x)%mod;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
ll sum=quick(2ll,n);
ll num=sum+mod-1;
ll res=1ll;
f[0]=1;
f[1]=0;
g[1]=num;
for(int i=2;i<=m;i++)
{
f[i]=g[i-1]-f[i-1]+mod;
f[i]-=((f[i-2]*(i-1))%mod*(sum-1-(i-2)))%mod;
f[i]=(f[i]%mod+mod)%mod;
g[i]=(g[i-1]*(num-i+1))%mod;
res*=1ll*i;
res%=mod;
}
ll ans=(f[m]*quick(res,mod-2))%mod;
printf("%lld",ans);
}