n太大，而k比较小，可以O(k^2)做

想方设法争取把有关n的循环变成O(1)的式子

考虑用公式：

来替换i^k

原始的组合数C(n,i)一项，考虑能否和后面的系数分离开来，直接变成2^n处理。

之后大力推式子

考虑要消掉n，就想办法把n往里面放，与和n有关的项外层枚举的话，相对就不动了。可以乘法分配律把n搞定。

 

 

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=5005;const int mod=1e9+7;int s[N][N];int C[N][N];ll qm(ll x,ll y){    ll ret=1;    while(y){        if(y&1) ret=ret*x%mod;        x=x*x%mod;        y>>=1;    }    return ret;}ll n,k;int main(){    scanf("%lld %lld",&n,&k);    if(n>k){        s[0][0]=1;        for(reg i=1;i<=k;++i){            for(reg j=1;j<=k;++j){                s[i][j]=((ll)s[i-1][j-1]+(ll)j*s[i-1][j]%mod)%mod;            }        }        ll jie=1;        ll ans=0;        for(reg j=1;j<=k;++j){            jie=jie*(n-j+1)%mod;            ll mi=qm(2,n-j);            ans=(ans+(ll)s[k][j]*jie%mod*mi%mod)%mod;        }        printf("%lld",ans);    }else{        C[0][0]=1;        for(reg i=1;i<=n;++i){            C[i][0]=1;            for(reg j=1;j<=n;++j){                C[i][j]=((ll)C[i-1][j]+C[i-1][j-1])%mod;            }        }        ll ans=0;        for(reg i=1;i<=n;++i){            ans=(ans+(ll)C[n][i]*qm(i,k))%mod;        }        printf("%lld",ans);    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2018/12/28 19:46:50*/
      

推式子其实是下策（下下策是打表找规律。。。）

如果有组合意义的话，那么效果是立竿见影的。

意义是，n个盒子，从中选择i个出来，再把k个球往这i个盒子里放，可以不放的方案数总和。盒子不同球不同

k很小，没用的盒子很多，

转化研究对象，

考虑k个球最终占据了哪几个盒子。其他的盒子打酱油爱选不选。

那么直接就是：

一步搞定！