Description
一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）
Input
一行两个整数N,K
Output
一行为答案。
Sample Input
3 2
Sample Output
6
HINT
【样例说明】
假设原集合为{A,B,C}
则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}
【数据说明】
对于100%的数据，1≤N≤1000000；0≤K≤N；
Solution
首先考虑一下容斥
设$f(k)$表示选出一些集合使它们交集大小至少为$k$的方案数。
那么$f(k)=C_n^k \times (2^{2^{n-k}}-1)$
这玩意儿怎么理解呢？也就是先把那$i$个数确定下来，然后有$2^{n-k}$个集合可以包含那$k$个数。这些集合要么选要么不选，但不能一个都不选，也就是不能为空集。所以有$2^{2^{n-k}}-1$种选择方法。
那么容斥系数呢？可以发现当计算交集至少为$k$的方案时候，交集至少为$j$的方案（$j>k$）会被计算$C_j^k$次。
也就是说，
$f(k)$的系数为$1$。
$f(k+1)$的系数为$-C_{k+1}^k$。
$f(k+2)$的系数为$-C_{k+2}^k+C_{k+1}^k\times C_{k+2}^{k+1}=C_{k+2}^k$
为什么$f(k+2)$能那么推呢……因为$C_N^M\times C_M^S=C_N^S\times C_{N-S}^{N-M}$
搞到现在基本可以组合计数搞搞出解了，至于那个大的一比的$2^{2^{n-k}}$，根据欧拉定理直接指数取模$φ(MOD)$就好了，显然$φ(MOD)=MOD-1$。
Code
#include<iostream>
#include<cstdio>
#define N (1000009)
#define LL long long
#define MOD (1000000007)
using namespace std; LL n,k,ans,inv[N],fac[N],facinv[N],p[N]; void Init()
{
inv[]=fac[]=facinv[]=p[]=;
for (int i=; i<=n; ++i)
{
if (i!=) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
fac[i]=fac[i-]*i%MOD; facinv[i]=facinv[i-]*inv[i]%MOD;
p[i]=p[i-]*%(MOD-);
}
} LL Qpow(LL a,LL b)
{
LL ans=;
while (b)
{
if (b&) ans=ans*a%MOD;
a=a*a%MOD; b>>=;
}
return ans;
} LL C(LL n,LL m)
{
if (n<m) return ;
return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;
} int main()
{
scanf("%lld%lld",&n,&k);
Init();
for (int i=k,j=; i<=n; ++i,j=-j)
ans+=j*C(n,i)*(Qpow(,p[n-i])-)%MOD*C(i,k)%MOD;
ans=(ans%MOD+MOD)%MOD;
printf("%lld\n",ans);
}