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；
先选出k个(inom{n}{k})，这下的集合随便选，但是不能有交集
那么交集为(emptyset)=任意选(-)交集(geqslant 1)的方案数(+)交集(geqslant 2)的方案数(-)...
交集(geqslant i)就是选出(i)个元素来，剩下的随便选
所以就是(sumlimits_{i=0}^ninom{n}{i}(2^{2^{n-i}}-1))，减一是因为不能都不选
组合数直接预处理逆元，(2^{2^i})可以先把(2^i)预处理出来，取模用费马小定理——(a^{p-1}equiv 1(\%p))，(p)为质数
其实也可以考虑(2^{2^i}=2^{2^{i-1}}2^{2^{i-1}})，然后一路平方过来即可
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1e6,p=1e9+7;
int fac[N+10],inv[N+10],g[N+10];
void prepare(){
fac[0]=inv[0]=inv[1]=g[0]=1;
for (int i=1;i<=N;i++) g[i]=2ll*g[i-1]%(p-1);
for (int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%p;
for (int i=2;i<=N;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
for (int i=1;i<=N;i++) inv[i]=1ll*inv[i-1]*inv[i]%p;
}
int C(int n,int m){return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;}
int mlt(int a,int b){
int res=1;
for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
return res;
}
int main(){
prepare();
int n=read(),k=read(),Ans=0; n=n-k;
for (int i=0;i<=n;i++) Ans=(Ans+1ll*(i&1?-1:1)*C(n,i)*(mlt(2,g[n-i])-1)%p+p)%p;
Ans=1ll*Ans*C(n+k,k)%p;
printf("%d
",Ans);
}