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个\(\binom{n}{k}\)，这下的集合随便选，但是不能有交集

那么交集为\(\emptyset\)=任意选\(-\)交集\(\geqslant 1\)的方案数\(+\)交集\(\geqslant 2\)的方案数\(-\)...

交集\(\geqslant i\)就是选出\(i\)个元素来，剩下的随便选

所以就是\(\sum\limits_{i=0}^n\binom{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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing 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\n",Ans);}