Codeforces 932E Team work
You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is xk.
Output the sum of costs over all non-empty subsets of people.
Input
Only line of input contains two integers N (1 ≤ N ≤ 109) representing total number of people and k (1 ≤ k ≤ 5000).
Output
Output the sum of costs for all non empty subsets modulo 109 + 7.
Examples
input
1 1
output
1
input
3 2
output
24
Note
In the first example, there is only one non-empty subset {1} with cost 11 = 1.
In the second example, there are seven non-empty subsets.
- {1} with cost 12 = 1
- {2} with cost 12 = 1
- {1, 2} with cost 22 = 4
- {3} with cost 12 = 1
- {1, 3} with cost 22 = 4
- {2, 3} with cost 22 = 4
- {1, 2, 3} with cost 32 = 9
The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.
#include<bits/stdc++.h>
using namespace std;
#define N 5010
#define yyf 1000000007
#define LL long long
LL S[N][N],inv[N],C[N],J[N];
LL n,k;
LL fast_pow(LL a,LL b){
LL ans=1;
while(b){
if(b&1)ans=ans*a%yyf;
b>>=1;
a=a*a%yyf;
}
return ans;
}
int main(){
cin>>n>>k;
inv[0]=inv[1]=1;C[1]=n;J[1]=1;
for(LL i=2;i<=k;i++)J[i]=J[i-1]*i%yyf;
for(LL i=2;i<=k;i++)inv[i]=(yyf-yyf/i)*inv[yyf%i]%yyf;
for(LL i=2;i<=k;i++)C[i]=C[i-1]*inv[i]%yyf*(n-i+1)%yyf;
S[0][0]=1;
for(LL i=1;i<=k;i++){
S[i][0]=0;
for(LL j=1;j<=i;j++)S[i][j]=(j*S[i-1][j]%yyf+S[i-1][j-1])%yyf;
}
LL ans=0;
for(LL i=1;i<=min(k,n);i++)ans=(ans+S[k][i]*J[i]%yyf*C[i]%yyf*fast_pow(2,n-i)%yyf)%yyf;
printf("%lld",ans%yyf);
return 0;
}