stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int k,l,cnt;

char s[5005];

string ch[5005*6];

int main(){

	scanf("%s%d",s,&k);

	l=strlen(s);

	for(int i=0,T;i<l;++i){

		ch[++cnt]=s[i];

		T=min(k,l-i);

		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];

	}

	sort(ch+1,ch+cnt+1);

	unique(ch+1,ch+cnt+1);

	cout<<ch[k];

}

// Faster C++ solution for the same problem (measured speedup: 2.1558081806120897x):
#include<set>

#include<cstdio>

#include<cstring>

using namespace std;

struct str{

	char a[5];

	bool operator < (const str &p) const

	{

		int i;

		for (i=0;i<5 && a[i]==p.a[i];i++) ;

		return a[i]<p.a[i];

	}

}p;

set <str> que;

char s[5001];

int main()

{

	set <str> :: iterator it;

	int l,k;

	bool b=false;

	scanf("%s",s);

	scanf("%d",&k);

 	l=strlen(s);

 	for (int i=0;i<l;i++)

 	{

 		for (int j=0;j<k;j++) p.a[j]='\0';

 		for (int j=0;j<k && i+j<l;j++)

 		{

 			p.a[j]=s[i+j];

 			if (!que.count(p)) 

			{

				que.insert(p);

				it=que.end();

				if (b) que.erase(*(--it));

 				else if (que.size()>=k) b=true;

			}

 		}

 	}

	 it=que.end();

	printf("%s",(*(--it)).a);

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int k,l,cnt;

char s[5005];

string ch[5005*6];

int main(){

	scanf("%s%d",s,&k);

	l=strlen(s);

	for(int i=0,T;i<l;++i){

		ch[++cnt]=s[i];

		T=min(k,l-i);

		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];

	}

	sort(ch+1,ch+cnt+1);

	unique(ch+1,ch+cnt+1);

	cout<<ch[k];

}

// Faster C++ solution for the same problem (measured speedup: 1.949180340398065x):
#include<bits/stdc++.h>

using namespace std;

string s;

int k;

vector<string>v;

set<string>ss;

int main()

{

	cin>>s>>k;

	for(int i=0;i<s.size();i++)

	{

		for(int j=1;j<=5;j++)

		{

			if(i+j>s.size())

			{

				break;

			}

			ss.insert(s.substr(i,j));

		}

	}

	for(set<string>::iterator it=ss.begin();it!=ss.end();it++)

	{

		v.push_back(*it);

	}

	sort(v.begin(),v.end());

	cout<<v[k-1]<<endl;

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int k,l,cnt;

char s[5005];

string ch[5005*6];

int main(){

	scanf("%s%d",s,&k);

	l=strlen(s);

	for(int i=0,T;i<l;++i){

		ch[++cnt]=s[i];

		T=min(k,l-i);

		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];

	}

	sort(ch+1,ch+cnt+1);

	unique(ch+1,ch+cnt+1);

	cout<<ch[k];

}

// Faster C++ solution for the same problem (measured speedup: 1.972693967805551x):
/***********************

*  Author: xuziyuan    * 

***********************/



#include <bits/stdc++.h>



#define rt0 return 0

#define rep(i,n) for(int i=0;i<n;i++)

#define repn(i,n) for(int i=1;i<=n;i++)

#define replet(c) for(char c='a';c<='z';c++) 

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

#define sqr(a) ((a)*(a))



using namespace std;



const LL MOD=1e9+7;



string s,t;

int k;

vector <string> v;



int main()

{

	cin>>s>>k;

	int sz=s.size();

	rep(i,sz)

	{

		t="";

		for(int j=i;j<sz&&j-i<k;j++)

		{

			t.pb(s[j]);

			v.pb(t);

		}

	}

	sort(v.begin(),v.end());

	v.erase(unique(v.begin(),v.end()),v.end());

	cout<<v[k-1]<<endl;

	rt0;

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int k,l,cnt;

char s[5005];

string ch[5005*6];

int main(){

	scanf("%s%d",s,&k);

	l=strlen(s);

	for(int i=0,T;i<l;++i){

		ch[++cnt]=s[i];

		T=min(k,l-i);

		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];

	}

	sort(ch+1,ch+cnt+1);

	unique(ch+1,ch+cnt+1);

	cout<<ch[k];

}

// Faster C++ solution for the same problem (measured speedup: 1.9717691758903497x):
#include <bits/stdc++.h>

using namespace std;

set<string> s;

set<string>::iterator it;

int main()

{

    string str;

    int k;

    cin >> str >> k;



    for (int i = 0; i < str.size(); i++)

    {

        for (int j = 1; j <= 5; j++)

        {

            s.insert(str.substr(i, j));

        }

    }



    for (int i = 1; i <= k - 1; i++)

        s.erase(s.begin());

    cout << (*(s.begin())) << endl;



    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int k,l,cnt;

char s[5005];

string ch[5005*6];

int main(){

	scanf("%s%d",s,&k);

	l=strlen(s);

	for(int i=0,T;i<l;++i){

		ch[++cnt]=s[i];

		T=min(k,l-i);

		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];

	}

	sort(ch+1,ch+cnt+1);

	unique(ch+1,ch+cnt+1);

	cout<<ch[k];

}

// Faster C++ solution for the same problem (measured speedup: 1.9383185624790693x):
#include <bits/stdc++.h>

using namespace std;

typedef long long Long;



struct state{

	Long len, link;

	map<char,int> next;

	state(){}

	state(Long len, Long link) : len(len), link(link){}

};



struct suffixAutomaton{

	vector<state> st;

	Long sz, last;

	

	suffixAutomaton(){}

	suffixAutomaton(Long n){

		st.resize(n << 1ll);

		last = 0;

		st[0].len = 0;

		st[0].link = -1;

		sz = 1;

	}

	

	void addChar(char c){

		Long cur = sz++;

		st[cur].len = st[last].len + 1;

		Long p = last;

		while(p != -1 && !st[p].next.count(c)){

			st[p].next[c] = cur;

			p = st[p].link;

		}

		if(p == -1){

			st[cur].link = 0;

		}else{

			Long q = st[p].next[c];

			if(st[p].len + 1 == st[q].len){

				st[cur].link = q;

			}else{

				Long clone = sz++;

				st[clone].len = st[p].len + 1;

				st[clone].next = st[q].next;

				st[clone].link = st[q].link;

				while(p != -1 && st[p].next[c] == q){

					st[p].next[c] = clone;

					p = st[p].link;

				}

				st[q].link = st[cur].link = clone;

			}

		}

		last = cur;

	}

	

	void build(string &s){

		for(char c : s) addChar(c);

		return;

	}

};





const Long MX = 1e4 + 10;

suffixAutomaton sa;

Long memo[MX];

bool used[MX];

bool ok;

string ans;



Long dp(Long u){

	if(used[u]) return memo[u];

	used[u] = true;

	memo[u] = 1;

	for(auto par : sa.st[u].next){

		memo[u] += dp(par.second);

	}

	return memo[u];

}



void reconstruct(Long u, Long l, Long r, Long k){

	if(l == k){

		ok = true;

		return;

	}

	Long aux = 1;

	for(auto par : sa.st[u].next){

		Long v = par.second;

		if(l + aux <= k && k <= l + aux + memo[v] - 1){

			reconstruct(v, l + aux, l + aux + memo[v] - 1, k);

			if(ok){

				ans += par.first;

				break;

			}

		}

		aux += memo[v];

	}

	return;

}



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cout.precision(10);

	cout << fixed;



	string s;

	cin >> s;

	Long k;

	cin >> k;

	k++;

	

	sa = suffixAutomaton(s.size());

	sa.build(s);

	dp(0);

	ok = false;

	ans = "";

	reconstruct(0,1,memo[0],k);

	reverse(ans.begin(),ans.end());

	cout << ans << "\n";

	return 0;

}
// Slower C++ solution:
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 1000

#define hlq 1000000007



using namespace std;

int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];

int DP(int l,int r,int res)

{

	if(res==0)

		return 1;

	if(r<l)

		return 0;

	if(~dp[r][res])

		return dp[r][res];

	dp[r][res]=DP(l,r-1,res);

	int i,k=min(d,res/r),f=1,t=res,tmp=0;

	if(c>k)

		return dp[r][res];

	for(i=1;i<c&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

	}

	for(i=c;i<=k&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

		tmp=1LL*DP(l,r-1,t)*f%hlq;

		tmp=1LL*tmp*fac[i]%hlq;

		dp[r][res]=(tmp+dp[r][res])%hlq;

	}

	return dp[r][res];

}

int pow_mod(long long a,int x)

{

	long long ans=1;

	while(x)

	{

		if(x&1)

			ans=ans*a%hlq;

		a=a*a%hlq;

		x>>=1;

	}

	return (int)ans;

}

int main()

{

	int n,a,b,i,j;

	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);

	memset(dp,-1,sizeof(dp));

	for(i=0;i<=n;i++)

	{

		C[i][0]=1;

		for(j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;

	}

	fac[0]=1;

	for(i=1;i<=n;i++)

		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;

	printf("%d",DP(a,b,n));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.022763900173654x):
#include <bits/stdc++.h>

#define PII pair<int, int>

#define LL long long

using namespace std;

const int MAXN = 1005;

const LL INF = (LL)1e9 + 5;

const LL MOD = 1000000007;



LL dp[MAXN][MAXN], inv[MAXN], c[MAXN][MAXN];



LL mod_inv(LL x) {

	LL pw = MOD - 2, res = 1;

	while (pw) {

		if (pw & 1) res = res * x % MOD;

		x = x * x % MOD;

		pw >>= 1;

	}

	return res;

}



LL solve(LL N, LL A, LL B, LL C, LL D) {

	dp[A - 1][0] = 1;

	fill(dp[A - 1] + 1, dp[A - 1] + MAXN, 0);

	for (int i = A; i <= B; i++) {

		for (int j = 0; j <= N; j++) {

			LL prod = 1;

			dp[i][j] = dp[i - 1][j];

			for (int k = 1; k <= D && k * i <= j; k++) {

				LL rem = j - k * i;

				prod = prod * inv[k] % MOD* c[rem + i][i] % MOD;

				if (k < C) continue;

				dp[i][j] = (dp[i][j] + prod * dp[i - 1][rem]) % MOD;

			}

		}

	}

	return dp[B][N];

}



int main() {

	ios_base::sync_with_stdio(0); cin.tie(0);



	LL N, A, B, C, D;

	cin >> N >> A >> B >> C >> D;

	

	for (int i = 1; i <= N; i++) {

		inv[i] = mod_inv(i);

	}

	

	for (int n = 0; n <= N; n++) {

		for (int k = 0; k <= n; k++) {

			c[n][k] = (k == 0 || k == n ? 1 : (c[n - 1][k] + c[n - 1][k - 1]) % MOD);

		}

	}

	

	cout << solve(N, A, B, C, D) << '\n';



	return 0;

}
// Slower C++ solution:
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 1000

#define hlq 1000000007



using namespace std;

int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];

int DP(int l,int r,int res)

{

	if(res==0)

		return 1;

	if(r<l)

		return 0;

	if(~dp[r][res])

		return dp[r][res];

	dp[r][res]=DP(l,r-1,res);

	int i,k=min(d,res/r),f=1,t=res,tmp=0;

	if(c>k)

		return dp[r][res];

	for(i=1;i<c&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

	}

	for(i=c;i<=k&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

		tmp=1LL*DP(l,r-1,t)*f%hlq;

		tmp=1LL*tmp*fac[i]%hlq;

		dp[r][res]=(tmp+dp[r][res])%hlq;

	}

	return dp[r][res];

}

int pow_mod(long long a,int x)

{

	long long ans=1;

	while(x)

	{

		if(x&1)

			ans=ans*a%hlq;

		a=a*a%hlq;

		x>>=1;

	}

	return (int)ans;

}

int main()

{

	int n,a,b,i,j;

	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);

	memset(dp,-1,sizeof(dp));

	for(i=0;i<=n;i++)

	{

		C[i][0]=1;

		for(j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;

	}

	fac[0]=1;

	for(i=1;i<=n;i++)

		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;

	printf("%d",DP(a,b,n));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.035040838229083x):
#include <bits/stdc++.h>

#define pb          emplace_back

#define ll          long long

#define fi          first

#define se          second

#define mp          make_pair

 

using namespace std;

 

const int N = int(2e3) + 7;

const int mod = int(1e9) + 7;

typedef pair<int, int> pii;

 

int n, a, b, c, d, f[N][N], fac[N], rev[N];

 

void add(int& x, int y) {if((x += y) >= mod) x -= mod;}

int mul(int x, int y) {return 1ll * x * y % mod;}

 

int Pow(int x, int y) {

   int res = 1;

   for(; y > 0; y >>= 1) {

       if(y & 1) res = mul(res, x);

       x = mul(x, x);

   }

   return res;

}

 

int32_t main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0), cout.tie(0);

    #define Task        "test"

    if(fopen(Task".inp", "r")) {

        freopen(Task".inp", "r", stdin);

        freopen(Task".out", "w", stdout);

    }

    cin >> n >> a >> b >> c >> d;

    fac[0] = 1;

    for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);

    rev[n] = Pow(fac[n], mod - 2);

    for(int i = n - 1; i >= 0; --i) rev[i] = mul(rev[i + 1], i + 1);

    for(int i = 0; i <= b; ++i) f[0][i] = 1;

    for(int i = 1; i <= n; ++i) {

       for(int j = a; j <= b; ++j) {

          for(int k = c; i - k * j >= 0 && k <= d; ++k)

             add(f[i][j], mul(f[i - k * j][j - 1], mul(Pow(rev[j], k), rev[k])));

          add(f[i][j], f[i][j - 1]);

          //cout << f[i][j] << ' ';

       }

       //cout << '\n';

    }

    cout << mul(f[n][b], fac[n]);

}
// Slower C++ solution:
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 1000

#define hlq 1000000007



using namespace std;

int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];

int DP(int l,int r,int res)

{

	if(res==0)

		return 1;

	if(r<l)

		return 0;

	if(~dp[r][res])

		return dp[r][res];

	dp[r][res]=DP(l,r-1,res);

	int i,k=min(d,res/r),f=1,t=res,tmp=0;

	if(c>k)

		return dp[r][res];

	for(i=1;i<c&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

	}

	for(i=c;i<=k&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

		tmp=1LL*DP(l,r-1,t)*f%hlq;

		tmp=1LL*tmp*fac[i]%hlq;

		dp[r][res]=(tmp+dp[r][res])%hlq;

	}

	return dp[r][res];

}

int pow_mod(long long a,int x)

{

	long long ans=1;

	while(x)

	{

		if(x&1)

			ans=ans*a%hlq;

		a=a*a%hlq;

		x>>=1;

	}

	return (int)ans;

}

int main()

{

	int n,a,b,i,j;

	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);

	memset(dp,-1,sizeof(dp));

	for(i=0;i<=n;i++)

	{

		C[i][0]=1;

		for(j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;

	}

	fac[0]=1;

	for(i=1;i<=n;i++)

		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;

	printf("%d",DP(a,b,n));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.039634990947872x):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cassert>



using namespace std;



const int MAXN = 1e3 + 7, MOD = 1e9 + 7;



int fact[MAXN], invfact[MAXN], dp[MAXN], N, A, B, C, D;



int bpow(int a, int p)

{

    int ans = 1;

    for (; p > 0; p >>= 1) {

        if (p & 1) {

            ans = 1ll * ans * a % MOD;

        }

        a = 1ll * a * a % MOD;

    }

    return ans;

}



int main()

{

    ios_base::sync_with_stdio(0); cin.tie(0);

    fact[0] = 1;

    for (int i = 1; i < MAXN; ++i) fact[i] = (1ll * fact[i - 1] * i) % MOD;

    invfact[MAXN - 1] = bpow(fact[MAXN - 1], MOD - 2);

    for (int i = MAXN - 1; i > 0; --i) invfact[i - 1] = 1ll * invfact[i] * i % MOD;



    dp[0] = 1;

    cin >> N >> A >> B >> C >> D;

    for (int x = A; x <= B; ++x) {

        for (int i = N; i >= x * C; --i) {

            for (int j = C; j <= D && j * x <= i; ++j) {

                long long add = dp[i - j * x];

                add = add * fact[N - (i - j * x)] % MOD;

                add = add * invfact[N - i] % MOD;

                add = add * bpow(invfact[x], j) % MOD;

                add = add * invfact[j] % MOD;

                dp[i] = ((dp[i] += add) >= MOD ? dp[i] - MOD : dp[i]);

            }

        }

    }



    cout << dp[N] << endl;

}
// Slower C++ solution:
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 1000

#define hlq 1000000007



using namespace std;

int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];

int DP(int l,int r,int res)

{

	if(res==0)

		return 1;

	if(r<l)

		return 0;

	if(~dp[r][res])

		return dp[r][res];

	dp[r][res]=DP(l,r-1,res);

	int i,k=min(d,res/r),f=1,t=res,tmp=0;

	if(c>k)

		return dp[r][res];

	for(i=1;i<c&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

	}

	for(i=c;i<=k&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

		tmp=1LL*DP(l,r-1,t)*f%hlq;

		tmp=1LL*tmp*fac[i]%hlq;

		dp[r][res]=(tmp+dp[r][res])%hlq;

	}

	return dp[r][res];

}

int pow_mod(long long a,int x)

{

	long long ans=1;

	while(x)

	{

		if(x&1)

			ans=ans*a%hlq;

		a=a*a%hlq;

		x>>=1;

	}

	return (int)ans;

}

int main()

{

	int n,a,b,i,j;

	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);

	memset(dp,-1,sizeof(dp));

	for(i=0;i<=n;i++)

	{

		C[i][0]=1;

		for(j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;

	}

	fac[0]=1;

	for(i=1;i<=n;i++)

		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;

	printf("%d",DP(a,b,n));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.713180364112797x):
#include <bits/stdc++.h>

#define int long long 



using namespace std;

const int somod = 1e9 + 7;

const int maxn = 1007;



int n, m, a, b, dp[maxn][maxn], c, d, fact[maxn], invfact[maxn], cac[maxn][maxn];



void Add(int &a, int b)

{

    a += b;

    if(a >= somod) a -= somod;

}



int Pow(int a, int b)

{

    int ans = 1;

    for(; b > 0; b >>= 1, a = a * a % somod)

    {

        if(b & 1) ans = ans * a % somod;

    }

    return ans;

}



void Prepare()

{

    fact[0] = 1;

    for(int i = 1; i < maxn; i++) fact[i] = fact[i - 1] * i % somod;

    invfact[maxn - 1] = Pow(fact[maxn - 1], somod - 2);

    for(int i = maxn - 2; i >= 0; i--) invfact[i] = (invfact[i + 1] * (i + 1)) % somod;

}



int C(int k, int n)

{

    return fact[n] * invfact[k] % somod * invfact[n - k] % somod;

}



int32_t main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin);

    Prepare();

    cin >> n >>a >> b >> c >> d;

    for(int i = 1; i < maxn; i++)

    {

        cac[i][0] = 1;

        for(int j = 1; j < maxn; j++)

        {

            if(i * j <= n) cac[i][j] = cac[i][j - 1] * C(i, j * i) % somod;

        }

    }

    dp[a - 1][0] = 1;

    for(int i = a; i <= b; i++)

    {

        for(int j = 1; j <= n; j++)

        {

            for(int k = c; k <= d; k++)

            {

                if(i * k > j) break;

                Add(dp[i][j], dp[i - 1][j - i * k] * C(i * k, n - j + i * k) % somod * cac[i][k] % somod * invfact[k] % somod);

            }

        }

        for(int j = 0; j <= n; j++) Add(dp[i][j], dp[i - 1][j]);

    }

    cout << dp[b][n];

}
// Slower C++ solution:
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 1000

#define hlq 1000000007



using namespace std;

int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];

int DP(int l,int r,int res)

{

	if(res==0)

		return 1;

	if(r<l)

		return 0;

	if(~dp[r][res])

		return dp[r][res];

	dp[r][res]=DP(l,r-1,res);

	int i,k=min(d,res/r),f=1,t=res,tmp=0;

	if(c>k)

		return dp[r][res];

	for(i=1;i<c&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

	}

	for(i=c;i<=k&&t>=r;i++)

	{

		f=(1LL*f*C[t][r])%hlq;

		t-=r;

		tmp=1LL*DP(l,r-1,t)*f%hlq;

		tmp=1LL*tmp*fac[i]%hlq;

		dp[r][res]=(tmp+dp[r][res])%hlq;

	}

	return dp[r][res];

}

int pow_mod(long long a,int x)

{

	long long ans=1;

	while(x)

	{

		if(x&1)

			ans=ans*a%hlq;

		a=a*a%hlq;

		x>>=1;

	}

	return (int)ans;

}

int main()

{

	int n,a,b,i,j;

	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);

	memset(dp,-1,sizeof(dp));

	for(i=0;i<=n;i++)

	{

		C[i][0]=1;

		for(j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;

	}

	fac[0]=1;

	for(i=1;i<=n;i++)

		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;

	printf("%d",DP(a,b,n));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.066079304256543x):
#include <bits/stdc++.h>

#define LL long long

using namespace std;

int n,a,b,c,d;

const int N=1003;

const int mod=1e9+7;

int f[N],dp[N],C[N][N],power[N],F[N][N];



int mu(int x,int m)

{

    if (m==1) return x;

    int c=mu(x,m/2);

    c=(LL)c*c%mod;

    if (m%2==0) return c;

    return (LL)c*x%mod;

}

int main()

{

   

    ios_base::sync_with_stdio(0);

    cin.tie(0);cout.tie(0);

    cin>>n>>a>>b>>c>>d;

    dp[0]=1;

    for (int i=0;i<=n;i++) C[i][i]=C[i][0]=1;

    for (int i=2;i<=n;i++)

    for (int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

    power[0]=1;

    for (int i=1;i<=n;i++) power[i]=((LL)power[i-1]*i)%mod;

    power[n]=mu(power[n],mod-2);

    for (int i=n-1;i>=0;i--) power[i]=(LL)power[i+1]*(i+1)%mod;

    for (int i=1;i<=n;i++) F[0][i]=1;

    for (int i=1;i<=n;i++)

    for (int j=i;j<=n;j+=i)

         F[j][i]=(LL)F[j-i][i]*C[j][i]%mod;

    for (int i=1;i<=n;i++)

    for (int j=i;j<=n;j+=i)

    {

        F[j][i]=(LL)F[j][i]*power[j/i]%mod;

        //cout<<j<<" "<<i<<" "<<F[j][i]<<"\n";

    }

    dp[0]=1;

    for (int i=a;i<=b;i++)

    {

        for (int h=0;h<=n;h++) f[h]=dp[h];

        for (int j=c;j<=d;j++)

        {

            int k=i*j;

            for (int h=k;h<=n;h++)

            {

                dp[h]=(dp[h]+((LL)f[h-k]*F[k][i]%mod)*C[n-h+k][k]%mod)%mod;

                //cout<<i<<" "<<j<<" "<<h<<" "<<dp[h]<<" "<<f[h-k]<<"\n";

            }

        }

    }

    cout<<dp[n];

    return 0;

}
// Slower C++ solution:
#include <iostream>

#define llint long long

#define mod 1000000007



using namespace std;



llint fact[2005], fact_i[2005];



llint pow(llint a, llint n)

{

	if(n == 0) return 1;

	if(n % 2){

		return ((a%mod) * (pow(a, n-1)%mod)) % mod;

	}

	else{

		return pow((a*a)%mod, n/2) % mod;

	}

}



void make_fact()

{

	llint val = 1;

	fact[0] = 1;

	for(int i = 1; i < 2005; i++){

		val *= i;

		val %= mod;

		fact[i] = val;

	}

	for(int i = 0; i < 2005; i++){

		fact_i[i] = pow(fact[i], mod-2);

	}

}



llint comb(llint n, llint k)

{

	llint ret = 1;

	ret *= fact[n];

	ret *= fact_i[k], ret %= mod;

	ret *= fact_i[n-k], ret %= mod;

	return ret;

}



llint N;

llint A, B, C, D;

llint dp[1005][1005];



int main(void)

{

	cin >> N;

	cin >> A >> B >> C >> D;

	make_fact();

	

	dp[0][0] = 1;

	llint val;

	for(int i = 0; i < N; i++){

		for(int j = 0; j <= N; j++){

			if(dp[i][j] == 0) continue;

			for(int k = 0; j + (i+1)*k <= N; k++){

				if(k != 0 && (i+1 < A || i+1 > B)) break;

				if(k != 0 && (k < C || k > D)) continue;

				val = 1;

				for(int l = 0; l < k; l++){

					val *= comb(N-j-(i+1)*l, i+1);

					val %= mod;

				}

				val *= fact_i[k];

				val %= mod;

				dp[i+1][j+(i+1)*k] += (dp[i][j] * val) % mod;

				dp[i+1][j+(i+1)*k] %= mod;

			}

		}

	}

	

	cout << dp[N][N] << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7309564986432078x):
#include <iostream>

#include <vector>

#include <utility>

#include <queue>

#include <stdio.h>

#include <math.h>

#include <algorithm>

#define llint long long

#define mod 1000000007

#define inf 1e18



using namespace std;

typedef pair<double, llint> P;

typedef pair<llint, P> E;



llint n;

llint a, b, c, d;

llint dp[1005][1005];



const int FACT_MAX = 2005;

llint fact[FACT_MAX], fact_inv[FACT_MAX];



llint modpow(llint a, llint n)

{

	if(n == 0) return 1;

	if(n % 2){

		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;

	}

	else{

		return modpow((a*a)%mod, n/2) % mod;

	}

}



void make_fact()

{

	llint val = 1;

	fact[0] = 1;

	for(int i = 1; i < FACT_MAX; i++){

		val *= i;

		val %= mod;

		fact[i] = val;

	}

	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);

	for(int i = FACT_MAX-2; i >= 0; i--){

		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;

	}

}



llint comb(llint n, llint k)

{

	llint ret = 1;

	ret *= fact[n];

	ret *= fact_inv[k], ret %= mod;

	ret *= fact_inv[n-k], ret %= mod;

	return ret;

}



int main(void)

{

	ios::sync_with_stdio(0);

	cin.tie(0);

	make_fact();

	

	cin >> n;

	cin >> a >> b >> c >> d;

	

	dp[a-1][0] = 1;

	for(int i = a-1; i < b; i++){

		for(int j = 0; j <= n; j++){

			dp[i+1][j] += dp[i][j],  dp[i+1][j] %= mod;

			llint mul = 1;

			for(int k = 1; k <= d && j+k*(i+1) <= n; k++){

				mul *= comb(n-j-(k-1)*(i+1), i+1), mul %= mod;

				if(k >= c){

					(dp[i+1][j+k*(i+1)] += dp[i][j] * mul % mod * fact_inv[k] % mod) %= mod;

				}

			}

		}

	}

	

	cout << dp[b][n] << endl;



	return 0;

}