集合计数

分析：

$$g[x]=C_n^x(2^{(2^{n-x})}-1)$$

$$g[x]=\sum_{i=x}^{n}C_i^xf[i]$$

$$f[x]=\sum_{i=x}^n(-1)^{i-x}C_i^xg[i]$$

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MOD 1000000007
#define MX 1000006

using namespace std;

typedef long long ll;

ll fac[MX], faci[MX], p2i[MX];
int n, k;

ll qpow(ll x, ll t)
{
ll ans = 1;
while(t)
{
if(t & 1) ans = ans*x%MOD;
x = x*x%MOD;
t >>= 1;
}
return ans;
}

ll inv(ll x) {return qpow(x, MOD-2);}

ll C(int n, int m) {return fac[n] * faci[m] % MOD * faci[n-m] % MOD;}

ll g[MX];

void init()
{
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
faci[n] = inv(fac[n]);
for(int i=n; i>=1; i--) faci[i-1] = faci[i] * i % MOD;
p2i[0] = 2;
for(int i=1; i<=n; i++) p2i[i] = p2i[i-1] * p2i[i-1] % MOD;
}

void work()
{
ll fk = 0;
for(int i=0; i<=n; i++) g[i] = C(n, i) * (p2i[n-i]-1) % MOD;
for(int i=k; i<=n; i++)
{
if((i^k) & 1) fk = (fk - C(i, k) * g[i]) % MOD;
else fk = (fk + C(i, k) * g[i]) % MOD;
}
printf("%lld\n", (fk+MOD)%MOD);
}

int main()
{
scanf("%d%d", &n, &k);
init();
work();
return 0;
}