题意
(n) 个元素可以构成 (2^n) 种集合（包括空集），求在其中选出大于等于一个集合，使得这些集合的交的大小为 (k) 。
(0le kle nle 10^6) 。
分析
选出 (k) 个作为交集，那么问题转化成在 (n-k) 个元素组成的集合中选出大于等于一个集合，使得它们的交集为空。
对这个东西进行容斥，用交集至少为0-交集至少为1+交集至少为2……，即若要求 (n) 个元素组成交集为空的方案数：
[sum _{i=0}^n(-1)^iinom n i (2^{2^{n-i}}-1)
]
即容斥，决定交集是什么，剩下的 (n-i) 个元素又组成 (2^{n-i}) 种集合，可以任取，但是不能取空集。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long giant;
const int maxn=1e6+1;
const int q=1e9+7;
inline int Plus(int x,int y) {return ((giant)x+(giant)y)%q;}
inline int Sub(int x,int y) {return Plus(x,q-y);}
inline int Multi(int x,int y) {return (giant)x*y%q;}
int inv[maxn],fac[maxn],ifac[maxn],n,k;
inline int C(int n,int m) {return Multi(Multi(fac[n],ifac[m]),ifac[n-m]);}
inline int mi(int x,int y,int t=0) {
if (!t) t=q;
int ret=1;
for (;y;y>>=1,x=(giant)x*x%t) if (y&1) ret=(giant)ret*x%t;
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
cin>>n>>k;
inv[1]=fac[1]=ifac[1]=fac[0]=ifac[0]=1;
for (int i=2;i<=n;++i) {
inv[i]=Multi(q-q/i,inv[q%i]);
fac[i]=Multi(fac[i-1],i);
ifac[i]=Multi(ifac[i-1],inv[i]);
}
int ans=C(n,k),aux=0;
n-=k;
for (int i=0;i<=n;++i) {
int tmp=Multi(C(n,i),Sub(mi(2,mi(2,n-i,q-1)),1));
aux=Plus(aux,i&1?q-tmp:tmp);
}
ans=Multi(ans,aux);
printf("%d
",ans);
return 0;
}