看计数想容斥

考虑强制选 $K$ 个数作为子集，剩下数组成的集合随便选几个子集使得它们交集为空

显然 $n$ 个数中强制选 $K$ 个数的方案数是 $C_{n}^{K}$

剩下的数构成的子集总数有 $2^{n-K}$ 个，那么如果没有交集为空的限制方案数就是 $2^{2^{n-K}}-1$（注意要 $-1$，因为空集取和不取是一样的）

那么根据乘法原理显然，交集元素个数 至少 为 $K$ 的方案数就是 $C_{n}^{K} (2^{2^{n-K}}-1) $

设 $F_{i}$ 表示交集元素个数至少为 $i$ 的方案数

根据容斥，剩下的数交集为空的方案数就是 $F_{0}-F_{1}+F_{2}-F_{3}+...+(-1)^{n-K}F_{n-K}$

把交集为空的方案数乘上强制选 $K$ 个数作为子集的方案数 $C_{n}^{K}$ 就好了

注意到算 $F_{i}$ 时要算 $2^{2^{n-i}}$ ，发现 $2^{2^{n-i}} = 2^{2^{n-i-1}} \cdot 2^{2^{n-i-1}}$

然后预处理阶乘和阶乘逆元就好了，具体看代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}const int N=1e6+7,mo=1e9+7;int n,K,ans;ll fac[N],facinv[N],inv[N];inline ll C(int x,int y) { return fac[x]*facinv[y]%mo*facinv[x-y]%mo; }inline ll fk(ll x) { return x>=mo ? x-mo : x; }int main(){    n=read(),K=read();    fac[0]=1; facinv[0]=1; inv[1]=1;    for(int i=1;i<=n;i++)    {        if(i!=1) inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;        fac[i]=fac[i-1]*i%mo;        facinv[i]=facinv[i-1]*inv[i]%mo;    }    ll now=2; n-=K;    for(int i=n;i>=0;i--)    {        if(i&1) ans=( ans - C(n,i)*(now-1)%mo +mo )%mo;        else ans=fk( ans + C(n,i)*(now-1)%mo );        now=now*now%mo;    }    printf("%lld",ans*C(n+K,K)%mo);    return 0;}