题意：

戳这里

分析：

• 前置芝士：第二类斯特林数

首先先写出第二类斯特林数将普通幂转化为下降幂的式子：

\(\displaystyle i^k=\sum_{j=0}^kS_k^j\frac{i!}{(i-j)!}\)

然后开始大力推柿子

\[\sum_{i=1}^nC_n^i i^k \\ =\sum_{i=1}^nC_n^i\sum_{j=0}^kS_k^j\frac{i!}{(i-j)!} \\ =\sum_{i=1}^nC_n^i\sum_{j=0}^kj!S_k^jC_i^j \\ =\sum_{j=0}^kj!S_k^j\sum_{i=1}^n\frac{n!i!}{(n-i)!i!(i-j)!j!} \]

关键的一步来了，我们发现原来的瓶颈在于组合数的处理，所以我们要考虑优化组合数的计算，把两项组合数混在一起重新组合

\[=\sum_{j=0}^kj!S_k^j\sum_{i=1}^n\frac{n!(n-j)!}{(n-i)!(n-j)!(i-j)!j!} \\ =\sum_{j=0}^kj!S_k^j\sum_{i=1}^n\frac{n!}{(n-j)!j!}\frac{(n-j)!}{(n-i)!(i-j)!} \\ =\sum_{j=0}^kj!S_k^j\sum_{i=1}^nC_n^jC_{n-j}^{i-j} \\ =\sum_{j=0}^kj!S_k^jC_n^j\sum_{i=j}^nC_{n-j}^{i-j} \\ =\sum_{j=0}^kj!S_k^jC_n^j2^{n-j} \\ =\sum_{j=0}^k\frac{n!}{(n-j)!}S_k^j2^{n-j} \]

然后我们可以 \(O(k^2)\) 预处理出所有我们需要的东西

• 另解：

其实算到这里已经可以 A 掉这道题了，但是其实还是有一些更优的办法，比如说我们预处理 Strling 数的复杂度是 \(O(k^2)\) ，但是第二类斯特林数有一个通项公式 \(\displaystyle S_k^n=\sum_{i=0}^n\frac{(-1)^i}{i!}\frac{(n-i)^k}{(n-i)！}\)，这是一个卷积的形式可以用 NTT 优化到 \(O(n\log)\) 但是这个题模数不对劲/kk

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
    typedef long long ll;
    const ll maxn = 5005;
    const ll mod = 1e9+7;
    ll s[maxn][maxn];
    ll n,k,ans=0;

    ll qpow(ll x,ll y)
    {
        ll res=1;
        while(y)
        {
            if(y&1) res=res*x%mod;
            x=x*x%mod;
            y>>=1;
        }
        return res;
    }
    
    void init()
    {
        s[0][0]=1;
        for(int i=1;i<=5000;i++)
        {
            for(int j=1;j<=i;j++)
            {
                s[i][j]=(s[i-1][j-1]+s[i-1][j]*j%mod)%mod;
            }
        }
    }

    void work()
    {
        init();
        scanf("%lld%lld",&n,&k);
        ll fac=1,pw=qpow(2,n);
        for(ll j=0;j<=k;j++)
        {
            ans=(ans+fac*s[k][j]%mod*pw%mod)%mod;
            fac=fac*(n-j)%mod;
            pw=pw*qpow(2,mod-2)%mod;
        }
        printf("%lld\n",ans);
    }

}

int main()
{
    zzc::work();
    return 0;
}