stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
/*--------------------------------

  Author: The Ace Bee

  Blog: www.cnblogs.com/zsbzsb

  This code is made by The Ace Bee

--------------------------------*/

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}



typedef long long LL;

const int p = 1000000007;

const int _ = 410;



int n, c, a[_], b[_];

LL pw[_][_], f[_][_];



int main() {

	read(n), read(c);

	for (rg int i = 1; i <= n; ++i) read(a[i]);

	for (rg int i = 1; i <= n; ++i) read(b[i]);



	for (rg int i = 1; i < _; ++i) pw[i][0] = 1ll;

	for (rg int i = 1; i < _; ++i)

		for (rg int j = 1; j < _; ++j)

			pw[i][j] = 1ll * pw[i][j - 1] * i % p;

	

	for (rg int i = 1; i < _; ++i)

		for (rg int j = 0; j < _; ++j)

			pw[i][j] = (pw[i][j] + pw[i - 1][j]) % p;



	f[0][0] = 1;

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

		for (rg int j = 0; j <= c; ++j)

			for (rg int k = 0; k <= j; ++k)

				f[i][j] = (f[i][j] + 1ll * f[i - 1][j - k] * (pw[b[i]][k] - pw[a[i] - 1][k] + p) % p) % p;



	printf("%lld\n", f[n][c]);

	

	return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#define mod 1000000007

#define ll long long

using namespace std;



ll qpow(ll x,ll t){

	ll ans=1;

	while(t){

		if(t&1)ans=(ans*x)%mod;

		x=(x*x)%mod;

		t>>=1;

	}

	return ans%mod;

}



ll n,c,a[410],b[410],dp[2][401][401];



int main(){

	scanf("%lld %lld",&n,&c);

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

		scanf("%lld",&a[i]);

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

		scanf("%lld",&b[i]);



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

		for(int k=a[1];k<=b[1];k++){

			dp[1%2][j][k]=qpow(k,j)%mod;

			dp[1%2][j][0]+=dp[1][j][k];

			dp[1%2][j][0]%=mod;

		}

	

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

		

		memset(dp[i%2],0,sizeof(dp[i%2]));

		

		for(int k=a[i];k<=b[i];k++)

			dp[(i)%2][0][k]=dp[(i-1)%2][0][0];

		

		for(int k=a[i];k<=b[i];k++){

			for(int j=1;j<=c;j++){

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

				dp[(i)%2][j][k]%=mod;

				

				dp[(i)%2][j][k]+=dp[(i-1)%2][j][0];

				dp[(i)%2][j][k]%=mod;

			}

		}

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

			for(int k=a[i];k<=b[i];k++)		

				dp[(i)%2][j][0]=(dp[(i)%2][j][k]+dp[(i)%2][j][0])%mod;

	}

	

	cout<<dp[n%2][c][0]%mod;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define maxn 405

#define ll long long

#define p 1000000007

ll sum[maxn][maxn],f[maxn][maxn];

int n,m,a[maxn],b[maxn];

int main()

{

	scanf("%d%d",&n,&m);

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

		scanf("%d",&a[i]);

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

		scanf("%d",&b[i]);

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

	{

		sum[i][0]=1;

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

			sum[i][j]=1ll*sum[i][j-1]*i%p;

	}

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

		for(int j=0;j<=400;++j)

			sum[i][j]+=sum[i-1][j],sum[i][j]%=p;

	f[0][0]=1;

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

		for(int j=0;j<=m;++j)

			for(int k=0;k<=j;++k)

			{

				f[i][j]+=0ll+1ll*f[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k])%p;

				f[i][j]%=p;

			}

	printf("%lld\n",(f[n][m]%p+p)%p);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#define mod 1000000007

#define ll long long

using namespace std;



ll qpow(ll x,ll t){

	ll ans=1;

	while(t){

		if(t&1)ans=(ans*x)%mod;

		x=(x*x)%mod;

		t>>=1;

	}

	return ans%mod;

}



ll n,c,a[410],b[410],dp[2][401][401];



int main(){

	scanf("%lld %lld",&n,&c);

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

		scanf("%lld",&a[i]);

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

		scanf("%lld",&b[i]);



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

		for(int k=a[1];k<=b[1];k++){

			dp[1%2][j][k]=qpow(k,j)%mod;

			dp[1%2][j][0]+=dp[1][j][k];

			dp[1%2][j][0]%=mod;

		}

	

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

		

		memset(dp[i%2],0,sizeof(dp[i%2]));

		

		for(int k=a[i];k<=b[i];k++)

			dp[(i)%2][0][k]=dp[(i-1)%2][0][0];

		

		for(int k=a[i];k<=b[i];k++){

			for(int j=1;j<=c;j++){

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

				dp[(i)%2][j][k]%=mod;

				

				dp[(i)%2][j][k]+=dp[(i-1)%2][j][0];

				dp[(i)%2][j][k]%=mod;

			}

		}

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

			for(int k=a[i];k<=b[i];k++)		

				dp[(i)%2][j][0]=(dp[(i)%2][j][k]+dp[(i)%2][j][0])%mod;

	}

	

	cout<<dp[n%2][c][0]%mod;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

//#include<ext/rope>

//using namespace __gnu_cxx

//#include<ext/pb_ds/priority_queue.hpp>

//using namespace __gnu_pbds;

#define lowbit(x) (x&-x)

#define pb push_back

#define empb emplace_back

#define all(x) (x).begin(),(x).end()

#define clr(a,b) memset(a,b,sizeof(a))

#define caze(T) for(cin>>T;T;T--)

#define inf (1<<29)

#define Endl ('\n')

#define fi first

#define se second

#define db double

#define ldb long double

#define ll long long

#define pii pair<int,int>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pll pair<ll,ll>

#define ull unsigned long long

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

inline char nc() {

	#define SZ 1000000

	static char buf[SZ], *p1, *p2;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;

}

template<typename T>

inline int scan(T &x) {

	char c, sign=1; 

	while(!isdigit(c=nc())&&c!=EOF)if(c=='-')sign*=-1;

	if(c==EOF) return EOF;

	for(x = 0; isdigit(c); c = nc())

		x = (x<<1) + (x<<3) + (c&15);

	return x *= sign, 1;

}

template<typename T, typename...Args>

inline int scan(T &x, Args&...args) {

	return scan(x), scan(args...);

}

const int N=1<<9;

const int mod=1000000007;

int s[N][N];

int dp[N][N];

int l[N],r[N];

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

int sum(int k,int a,int b){int ret=s[k][b]-s[k][a-1]+mod;ret%=mod;return ret;}

int main()

{IOS;

	int n,k;cin>>n>>k;

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

		cin>>l[i];

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

		cin>>r[i];

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

		s[0][i]=1;

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

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

			s[i][j]=1LL*s[i-1][j]*j%mod;

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

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

			(s[i][j]+=s[i][j-1])%=mod;

	dp[0][0]=1;

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

		for(int j=0;j<=k;++j)

			for(int o=0;o<=j;++o)

				upd(dp[i][j],1LL*dp[i-1][j-o]*sum(o,l[i],r[i])%mod);

	cout<<dp[n][k]<<Endl;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#define mod 1000000007

#define ll long long

using namespace std;



ll qpow(ll x,ll t){

	ll ans=1;

	while(t){

		if(t&1)ans=(ans*x)%mod;

		x=(x*x)%mod;

		t>>=1;

	}

	return ans%mod;

}



ll n,c,a[410],b[410],dp[2][401][401];



int main(){

	scanf("%lld %lld",&n,&c);

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

		scanf("%lld",&a[i]);

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

		scanf("%lld",&b[i]);



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

		for(int k=a[1];k<=b[1];k++){

			dp[1%2][j][k]=qpow(k,j)%mod;

			dp[1%2][j][0]+=dp[1][j][k];

			dp[1%2][j][0]%=mod;

		}

	

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

		

		memset(dp[i%2],0,sizeof(dp[i%2]));

		

		for(int k=a[i];k<=b[i];k++)

			dp[(i)%2][0][k]=dp[(i-1)%2][0][0];

		

		for(int k=a[i];k<=b[i];k++){

			for(int j=1;j<=c;j++){

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

				dp[(i)%2][j][k]%=mod;

				

				dp[(i)%2][j][k]+=dp[(i-1)%2][j][0];

				dp[(i)%2][j][k]%=mod;

			}

		}

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

			for(int k=a[i];k<=b[i];k++)		

				dp[(i)%2][j][0]=(dp[(i)%2][j][k]+dp[(i)%2][j][0])%mod;

	}

	

	cout<<dp[n%2][c][0]%mod;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<ctime>

#include<vector>

#include<queue>

#include<map>

#include<deque>

#include<stack>

#include<algorithm>

#define N 405

using namespace std;

const int INF=0x7fffffff;

const double Pi=acos(-1);

const long long Mod=1e9+7;

long long A[N],B[N],P[N][N],Sum[N][N],F[N][N];

int main()

{

	int i,j,k,n,m;

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;i++)scanf("%lld",&A[i]);

	for(i=1;i<=n;i++)scanf("%lld",&B[i]);

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

	{

		P[i][0]=1;

		for(j=1;j<=400;j++)//P[i][j]=i^j

		{

			P[i][j]=P[i][j-1]*i%Mod;

		}

	}

	for(j=0;j<=400;j++)

	{

		Sum[0][j]=0;

		for(i=1;i<=400;i++)//Sum[i][j]=1^j+2^j+...+i^j 

		{

			Sum[i][j]=(Sum[i-1][j]+P[i][j])%Mod;

		}

	}

	F[0][0]=1;

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

	{

		for(j=0;j<=m;j++)

		{

			for(k=0;k<=j;k++)//Ã¶¾ÙµÚi¸öÈË·Ök¸ö 

			{

				long long Temp=(Sum[B[i]][k]-Sum[A[i]-1][k]+Mod)%Mod;

				F[i][j]=(F[i][j]+F[i-1][j-k]*Temp%Mod)%Mod;

			}

		}

	}

	printf("%lld\n",F[n][m]);

	return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#define mod 1000000007

#define ll long long

using namespace std;



ll qpow(ll x,ll t){

	ll ans=1;

	while(t){

		if(t&1)ans=(ans*x)%mod;

		x=(x*x)%mod;

		t>>=1;

	}

	return ans%mod;

}



ll n,c,a[410],b[410],dp[2][401][401];



int main(){

	scanf("%lld %lld",&n,&c);

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

		scanf("%lld",&a[i]);

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

		scanf("%lld",&b[i]);



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

		for(int k=a[1];k<=b[1];k++){

			dp[1%2][j][k]=qpow(k,j)%mod;

			dp[1%2][j][0]+=dp[1][j][k];

			dp[1%2][j][0]%=mod;

		}

	

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

		

		memset(dp[i%2],0,sizeof(dp[i%2]));

		

		for(int k=a[i];k<=b[i];k++)

			dp[(i)%2][0][k]=dp[(i-1)%2][0][0];

		

		for(int k=a[i];k<=b[i];k++){

			for(int j=1;j<=c;j++){

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

				dp[(i)%2][j][k]%=mod;

				

				dp[(i)%2][j][k]+=dp[(i-1)%2][j][0];

				dp[(i)%2][j][k]%=mod;

			}

		}

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

			for(int k=a[i];k<=b[i];k++)		

				dp[(i)%2][j][0]=(dp[(i)%2][j][k]+dp[(i)%2][j][0])%mod;

	}

	

	cout<<dp[n%2][c][0]%mod;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*  ***  In The Name of God ... ***  */ 

#include <bits/stdc++.h>

 

using namespace std;

 

typedef long long ll;

typedef long double ld;

 

 

#define int long long

#define all(v) v.begin() , v.end()



template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}

template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}



const int N = 400 + 10 , mod = 1e9 + 7 ;



int n , C , a [ N ] , b [ N ] , t [ N ] [ N ] , sum [ N ] [ N ] , dp [ N ] [ N ] ; 



int32_t main()

{

	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> C ;

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

		cin >> a [ i ] ;

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

		cin >> b [ i ] ;

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

		t [ i ] [ 0 ] = 1 ;

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

			( t [ i ] [ j ] = t [ i ] [ j - 1 ] * i ) %= mod ; 

		}

	}

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

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

			for ( int k = a [ i ] ; k <= b [ i ] ; ++ k )

				sum [ i ] [ j ] += t [ k ] [ j ] , sum [ i ] [ j ] %= mod ; 

		}

	}

	dp [ 0 ] [ 0 ] = 1 ; 

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

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

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

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

				dp [ i ] [ j ] %= mod ; 

			}

		}

	}/*

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

		for ( int want = 0 ; want <= C ; ++ want ) {

			cout << i << ' ' << want << ' ' << dp [ i ] [ want ] << '\n' ; 

		}

		}*/

	cout << dp [ n ] [ C ] % mod << '\n' ; 

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<vector>

using std::vector;

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define reg register

typedef long long ll;

inline int read(){

    reg int x=0,f=1;reg char ch=getchar();

    for(;!isdigit(ch);f=ch=='-'?-1:1,ch=getchar());

    for(;isdigit(ch);x=x*10+(ch^48),ch=getchar());

    return x*f;

}

const int mod=1e9+7;

int n,c;

int a[405],b[405],f[405][405];

ll prod[405][405];

inline ll qpow(ll a,ll b){

    reg ll res=1;

    while(b){

        if(b&1)res=res*a%mod;

        a=a*a%mod;b>>=1;

    }

    return res;

}

int main(){

    n=read();c=read();

    for(reg int i=1;i<=n;i++)a[i]=read();

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

        b[i]=read();prod[i][0]=b[i]-a[i]+1;

        for(reg int j=1;j<=c;j++)

            for(reg int k=a[i];k<=b[i];k++)prod[i][j]=(prod[i][j]+qpow(k,j))%mod;

    }

    f[0][0]=1;

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

        for(reg int j=0;j<=c;j++)

            for(reg int k=0;k<=j;k++)

                f[i][j]=(f[i][j]+1ll*f[i-1][j-k]*prod[i][k]%mod)%mod;

    printf("%d\n",f[n][c]);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

#define mod 1000000007

#define MN 405

long long f[MN][MN],pw[MN][MN],qz[MN][MN];

int n,c,a[MN],b[MN];

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

long long Abs(long long x){if(x<0) x+=mod;return x;}

int main(){

	register int i,j,k;

	for(i=1;i<=400;i++) pw[i][0]=1;

	

	for(i=1;i<=400;i++)for(j=1;j<=400;j++) pw[i][j]=(pw[i][j-1]*i)%mod;

	for(i=1;i<=400;i++)for(j=0;j<=400;j++) qz[i][j]=(qz[i-1][j]+pw[i][j])%mod;

	

	n=read(),c=read();

	for(i=1;i<=n;i++) a[i]=read();

	for(i=1;i<=n;i++) b[i]=read();

	

	f[0][0]=1;

	

	for(i=1;i<=n;i++)for(j=0;j<=c;j++)for(k=j;k>=0;k--){

		add(f[i][j],f[i-1][k]*Abs(qz[b[i]][j-k]-qz[a[i]-1][j-k])%mod);

	}

	printf("%lld\n",f[n][c]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<vector>

using std::vector;

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define reg register

typedef long long ll;

inline int read(){

    reg int x=0,f=1;reg char ch=getchar();

    for(;!isdigit(ch);f=ch=='-'?-1:1,ch=getchar());

    for(;isdigit(ch);x=x*10+(ch^48),ch=getchar());

    return x*f;

}

const int mod=1e9+7;

int n,c;

int a[405],b[405],f[405][405];

ll prod[405][405];

inline ll qpow(ll a,ll b){

    reg ll res=1;

    while(b){

        if(b&1)res=res*a%mod;

        a=a*a%mod;b>>=1;

    }

    return res;

}

int main(){

    n=read();c=read();

    for(reg int i=1;i<=n;i++)a[i]=read();

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

        b[i]=read();prod[i][0]=b[i]-a[i]+1;

        for(reg int j=1;j<=c;j++)

            for(reg int k=a[i];k<=b[i];k++)prod[i][j]=(prod[i][j]+qpow(k,j))%mod;

    }

    f[0][0]=1;

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

        for(reg int j=0;j<=c;j++)

            for(reg int k=0;k<=j;k++)

                f[i][j]=(f[i][j]+1ll*f[i-1][j-k]*prod[i][k]%mod)%mod;

    printf("%d\n",f[n][c]);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 401;

const int mod = 1e9 + 7;

inline int add(ll x, ll y) {return (x + y) % mod;}

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

inline int sub(ll x, ll y) {return (x - y + mod) % mod;}

int dp[N][N], sum[N][N], A[N], B[N];



int main()

{

    int n, c; scanf("%d%d", &n, &c);

    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);

    for (int i = 1; i <= n; i++) scanf("%d", &B[i]);

    for (int y = 1; y <= 400; y++)

        for (int x = 0, v = 1; x <= 400; x++, v = mul(v, y)) sum[x][y] = v;

    for (int x = 0; x <= 400; x++)

        for (int y = 1; y <= 400; y++) sum[x][y] = add(sum[x][y], sum[x][y - 1]);

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

    dp[0][c] = 1;

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

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

            for (int k = j; k <= c; k++) if (dp[i - 1][k] != -1)

            {

                if (dp[i][j] == -1) dp[i][j] = 0;

                int use = k - j;

                dp[i][j] = add(dp[i][j], mul(dp[i - 1][k], sub(sum[use][B[i]], sum[use][A[i] - 1])));

            }

    printf("%d\n", dp[n][0]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

const int maxn=410;

typedef long long ll;

int n,c;

const ll MOD=1e9+7;

ll a[maxn],b[maxn],f[maxn][maxn];

ll pwr[maxn][maxn],pre[maxn][maxn];

void preload()

{

    pre[0][0]=1;

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

    {

        pwr[i][0]=1;

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

        {

            pwr[i][j]=(pwr[i][j-1]%MOD*i)%MOD;

        }

    }

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

    {

        pre[i][0]=1;

        for(int j=0;j<=400;j++)

        {

            pre[i][j]=(pwr[i][j]+pre[i-1][j])%MOD;

        }

    }

}

int main()

{

    preload();

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

    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);

    f[0][0]=1;

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

    {

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

        {

            for(int k=0;k<=j;k++)

            {

                ll tmp=((pre[b[i]][k]-pre[a[i]-1][k])%MOD+MOD)%MOD;

                f[i][j]=(f[i][j]+f[i-1][j-k]*tmp)%MOD;

            }

        }

    }

    printf("%lld",f[n][c]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

const ll INF = 1e18;

const int BIG = 1e9 + 555;



int n;

map<ll, ll> mp;



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	cin >> n;



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

		ll x;	cin >> x;

		mp[x]++;

	}



	vector<ll> vv;

	

	ll fRes = 0;

	for(map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++){

		if(it->second < 2){

			continue;

		}

		vv.push_back(it->first);

		if(it->second >= 4){

			fRes = max(fRes, (it->first) * (it->first));

		}

	}

	

	if((int)vv.size() > 1){

		int L = (int)vv.size();

		fRes = max(fRes, vv[L - 2] * vv[L - 1]);

	}



	cout << fRes << '\n';



	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

 #define ll long long

  ll a[100005],b[100005];

using namespace std;

int main()

{

    int n;

    int flag=0;

    scanf("%d",&n);

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

    {

       scanf("%lld",&a[i]);

    }

    sort(a,a+n);

    int t=0;

    for(int j=n-1;j>=0;j--)

    {

        if(a[j]==a[j-1])

        {

            b[t]=a[j];

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

            t++;

            if(t==2)

            {

                flag=1;

                break;

            }

        }

    }

    if(flag==0)

        printf("0\n");

    else

    printf("%lld\n",b[0]*b[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



int main()

{

    int n,i;

    cin>>n;

    long long l[n];

    for(i=0;i<n;i++) cin>>l[i];

    sort(l,l+n);

    long long ans=0,x=0,y=0;

    for(i=n-1;i>0;)

    {

        if(x!=0 && y!=0) break;

        else if(x==0 && l[i]==l[i-1]) {

                x=l[i];

                i=i-2;

        }

        else if(x!=0 && l[i]==l[i-1]) {

                y=l[i];

                i=i-2;

        }

        else i--;

    }

    ans=x*y;

    cout<<ans<<"\n";

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

 #define ll long long

  ll a[100005],b[100005];

using namespace std;

int main()

{

    int n;

    int flag=0;

    scanf("%d",&n);

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

    {

       scanf("%lld",&a[i]);

    }

    sort(a,a+n);

    int t=0;

    for(int j=n-1;j>=0;j--)

    {

        if(a[j]==a[j-1])

        {

            b[t]=a[j];

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

            t++;

            if(t==2)

            {

                flag=1;

                break;

            }

        }

    }

    if(flag==0)

        printf("0\n");

    else

    printf("%lld\n",b[0]*b[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):


#include <bits/stdc++.h>

using namespace std;



#define LL long long



LL ara[100000+10];

//vector<LL>v;

LL v[100000+10];



LL abso(LL x)

{

	if(x<0)

		return -1*x;



	else

		return x;

}



int main() {



    LL n,cnt=0,ans=-1,k=1;

    scanf("%lld",&n);



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

    {

        scanf("%lld",&ara[i]);

    }



    sort(ara+1,ara+n+1);



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

    {

        if(ara[i]!=ara[i+1])

            cnt=0;



        if(ara[i]==ara[i+1])

        {

            cnt++;



            if(cnt+1==2)

            {

                v[k]=ara[i];

                k++;



            }



            if(cnt+1==4)

            {

                if(ara[i]*ara[i]>ans)

                {

                    ans=ara[i]*ara[i];

                    //cout<<"#*"<<ans<<endl;



                }



            }



        }

    }



    /*for(int i=1;i<=k;i++)

        cout<<v[i]<<" ";

*/

    //vector<LL>::iterator it = v.end();

    LL w = v[k-1];

    LL r = v[k-2];



    //cout<<"*"<<w<<" "<<r<<endl;



    LL ansi=w*r;



    if(ansi>ans)

        printf("%lld\n",ansi);



    else if(ansi<=ans)

        printf("%lld\n",ans);



    else

        printf("0\n");





	return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

 #define ll long long

  ll a[100005],b[100005];

using namespace std;

int main()

{

    int n;

    int flag=0;

    scanf("%d",&n);

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

    {

       scanf("%lld",&a[i]);

    }

    sort(a,a+n);

    int t=0;

    for(int j=n-1;j>=0;j--)

    {

        if(a[j]==a[j-1])

        {

            b[t]=a[j];

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

            t++;

            if(t==2)

            {

                flag=1;

                break;

            }

        }

    }

    if(flag==0)

        printf("0\n");

    else

    printf("%lld\n",b[0]*b[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main(){

	ll i,j,k,l,n;

	cin>>n;

	ll ar[n+1]; map<ll,ll> mp;

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

		cin>>ar[i];

		mp[ar[i]]++;

	}

	

	ll mx=-1; set<ll> st;

	for(auto it:mp){

		if(it.second>=4){

			mx=max(mx,it.first);

		}

		else if(it.second>=2){

			st.insert(it.first);

		}

	}



	

	ll mx2=-1,mx3=-1;

	if(st.size()>=1){

		mx3=max(mx3,mx*(*(--st.end())));

	}

		if(mx!=-1) mx=mx*mx;

	if(st.size()>=2){

		ll a,b;

		a=*(--st.end());

		st.erase(*(--st.end()));

		b=*(--st.end());

		mx2=max(mx2,a*b);

	}

	if(mx==-1&&mx2==-1){

		cout<<"0";

	}

	else{

		cout<<max(mx,max(mx2,mx3));

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

 #define ll long long

  ll a[100005],b[100005];

using namespace std;

int main()

{

    int n;

    int flag=0;

    scanf("%d",&n);

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

    {

       scanf("%lld",&a[i]);

    }

    sort(a,a+n);

    int t=0;

    for(int j=n-1;j>=0;j--)

    {

        if(a[j]==a[j-1])

        {

            b[t]=a[j];

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

            t++;

            if(t==2)

            {

                flag=1;

                break;

            }

        }

    }

    if(flag==0)

        printf("0\n");

    else

    printf("%lld\n",b[0]*b[1]);

}


// Fastest known solution for this problem: