comp[k] = How many ways a set of k elements can be written as a summation of few component.
Suppose S = {1, 2, 3}.
Here k = 3;
S = {1, 2, 3}
= {1, 2} + {3}
= {1, 3} + {2}
= {2, 3} + {1}
= {1} + {2} + {3}
So, comp[3] = 5.
/**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 4007 #define MOD 1000000007 #define POWMAX 7998007 int n; ll nCr[MAXX][MAXX]; ll ara[MAXX][MAXX]; ll comp[MAXX]; void calc() { ara[1][1] = 1; comp[0] = 1; comp[1] = 1; for(int i=2; i<MAXX; i++) { comp[i] = 1; ara[i][1] = 1; for(int j=2; j<=i; j++) { ara[i][j] = (ara[i-1][j-1] + (j * ara[i-1][j])%MOD )%MOD; comp[i] = (comp[i] + ara[i][j])%MOD; } } } int main() { calc(); nCr[1][0] = nCr[1][1] = 1; for(int i=2; i<MAXX; i++) { nCr[i][0] = 1; for(int j=1; j<=i; j++) { nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1])%MOD; } } cin>>n; ll ret = 0; for(int i=0; i<n; i++) { ll tmp = nCr[n][i] * comp[i]; ret = (ret + tmp%MOD)%MOD; } cout<<ret<<endl; }