stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<cstdio>

typedef long long ll;

const int MAXN = 400;

const int MOD = int(1E9) + 7;

int N, C, A[MAXN + 5], B[MAXN + 5];

ll Pow[MAXN + 5][MAXN + 5], D[MAXN + 5];

ll dp[MAXN + 5][MAXN + 5];

void init() {

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

		D[i] = 1;

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

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

			Pow[i][j] = Pow[i][j-1] + D[j];

			D[j] = D[j] * j % MOD;

		}

	}

}

int main() {

	init();

	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 i=0;i<=C;i++)

		dp[N][i] = (Pow[i][B[N]] - Pow[i][A[N]-1] + MOD) % MOD;

	for(int i=N-1;i>=1;i--) {

		for(int j=C;j>=0;j--) {

			for(int k=j;k>=0;k--) {

				dp[i][j] = (dp[i][j] + (Pow[k][B[i]] - Pow[k][A[i]-1] + MOD) % MOD * dp[i+1][j-k]) % MOD;

			}

		}

	}

	printf("%lld\n", dp[1][C]);

}

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

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

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

int n,c;

const long long mod=1e9+7;

int A[405],B[405];

long long matmod(long long val,long long k){

	long long ret=1;

	for(;k;k>>=1){

		if(k&1) ret=(val*ret)%mod;

		val=(val*val)%mod;

	}

	return ret;

}

void add(long long &des,long long sor){des+=sor;des%=mod;return ;}

long long sum[405][405],f[405][405];

int main(){

	//freopen("candies.in","r",stdin);

	//freopen("candies.out","w",stdout);

	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 i=0;i<=c;i++){

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

			add(sum[i][j],sum[i][j-1]+matmod(j*1ll,i*1ll));

	}

	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++)

				add(f[i][j],f[i-1][j-k]*(sum[k][B[i]]-sum[k][A[i]-1]+mod)%mod);

	}

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

	return 0;

}

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

#include<cstring>

const int MAXN=405,MOD=1000000007;



int N,C;

long long mpow[MAXN][MAXN],sum[MAXN][MAXN],dp[MAXN][MAXN];

int A[MAXN],B[MAXN];



int main()

{

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

	{

		mpow[i][0]=1;

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

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

	}

	

	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 i=0;i<=C;i++)

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

			for(int k=A[j];k<=B[j];k++)

				sum[i][j]=(sum[i][j]+mpow[k][i])%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][j]+dp[i-1][j-k]*sum[k][i]%MOD)%MOD;

	

	printf("%lld\n",dp[N][C]);

	

	return 0;

}


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

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

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

int n,c;

const long long mod=1e9+7;

int A[405],B[405];

long long matmod(long long val,long long k){

	long long ret=1;

	for(;k;k>>=1){

		if(k&1) ret=(val*ret)%mod;

		val=(val*val)%mod;

	}

	return ret;

}

void add(long long &des,long long sor){des+=sor;des%=mod;return ;}

long long sum[405][405],f[405][405];

int main(){

	//freopen("candies.in","r",stdin);

	//freopen("candies.out","w",stdout);

	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 i=0;i<=c;i++){

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

			add(sum[i][j],sum[i][j-1]+matmod(j*1ll,i*1ll));

	}

	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++)

				add(f[i][j],f[i-1][j-k]*(sum[k][B[i]]-sum[k][A[i]-1]+mod)%mod);

	}

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

	return 0;

}

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

#include<cstdio>

#include<cmath>

#include<cstring>



using namespace std;

#define ll long long

#define REP(i,e,s) for(register ll i=e; i<=s; i++)

#define DREP(i,e,s) for(register ll i=e; i>=s; i--)

#define DE(...) fprintf(stderr,__VA_ARGS__)

#define DEBUG(a) DE("DEBUG: %d\n",a)

#define int ll



int read() {

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

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

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

	return x*f;

}



const int MAXN=400+10,MOD=1e9+7;



int a[MAXN],b[MAXN],_pow[MAXN][MAXN],sum[MAXN][MAXN],f[MAXN][MAXN];



signed main() {

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

	REP(i,1,n) a[i]=read();

	REP(i,1,n) b[i]=read();

	

	REP(i,1,400) {

		_pow[i][0]=1;

		REP(j,1,400) _pow[i][j]=(_pow[i][j-1]*i)%MOD;

	}



	REP(i,1,400) REP(j,0,400) sum[i][j]=(sum[i][j]+sum[i-1][j]+_pow[i][j])%MOD;

	f[0][0]=1;	

	REP(i,1,n) REP(j,0,c) REP(k,0,j) f[i][j]=(f[i][j]+f[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k]+MOD)%MOD)%MOD;

	

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

	return 0;

}


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



using namespace std;



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << fixed << setprecision(15); 

    const int mod = 1000000007; 

    int n, m; 

    cin >> n >> m; 

    vector<int> a(n + 1), b(n + 1);

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) cin >> b[i]; 

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    vector<vector<int>> pw(n + 1, vector<int>(m + 1, 0)); 

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

        vector<int> tmp(b[i] - a[i] + 1, 1);  

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

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

                pw[i][j] = (pw[i][j] + tmp[k]) % mod; 

            }

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

                tmp[k] = 1ll * tmp[k] * (k + a[i]) % mod;

            } 

        }

    } 

    dp[0][0] = 1; 

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

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

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

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

            }

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

    return 0; 

}

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

#define MAXN 400+5

using namespace std;

typedef long long LL;

LL n,c,mod=1e9+7;

LL a[MAXN],b[MAXN];

LL f[MAXN][MAXN],s[MAXN][MAXN],sum[MAXN][MAXN];

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 i=1;i<=400;i++)

	{

		s[i][0]=1;

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

		{

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

		}

	}

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

	{

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

		{

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

		}

	}

	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++)

			{

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

			}

		}

	}

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

	return 0;

}


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



using namespace std;



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << fixed << setprecision(15); 

    const int mod = 1000000007; 

    int n, m; 

    cin >> n >> m; 

    vector<int> a(n + 1), b(n + 1);

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) cin >> b[i]; 

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    vector<vector<int>> pw(n + 1, vector<int>(m + 1, 0)); 

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

        vector<int> tmp(b[i] - a[i] + 1, 1);  

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

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

                pw[i][j] = (pw[i][j] + tmp[k]) % mod; 

            }

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

                tmp[k] = 1ll * tmp[k] * (k + a[i]) % mod;

            } 

        }

    } 

    dp[0][0] = 1; 

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

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

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

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

            }

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

    return 0; 

}

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

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=405;

ll c[maxn][maxn],sum[maxn][maxn];

ll a[maxn],b[maxn];

ll dp[maxn][maxn];

void init()

{

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

    {

        c[i][0]=1;c[i][1]=i;

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

        {

            c[i][j]=c[i][j-1]*i%mod;

        }

    }

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

    {

        sum[0][i]=c[0][i];

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

        {

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

        }

    }

}

int main()

{

    init();

    int n,c;

    while(~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]);

        memset(dp,0,sizeof(dp));

        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][j]+dp[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k]+mod)%mod)%mod;

                }

            }

        }

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

    }

}




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



using namespace std;



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << fixed << setprecision(15); 

    const int mod = 1000000007; 

    int n, m; 

    cin >> n >> m; 

    vector<int> a(n + 1), b(n + 1);

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) cin >> b[i]; 

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    vector<vector<int>> pw(n + 1, vector<int>(m + 1, 0)); 

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

        vector<int> tmp(b[i] - a[i] + 1, 1);  

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

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

                pw[i][j] = (pw[i][j] + tmp[k]) % mod; 

            }

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

                tmp[k] = 1ll * tmp[k] * (k + a[i]) % mod;

            } 

        }

    } 

    dp[0][0] = 1; 

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

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

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

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

            }

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

    return 0; 

}

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

#include<cstdio>

#include<cstring>

using namespace std;



long long f[405][405];

long long clz=1E9+7;

long long a[405],b[405];

long long n,c;

long long sm[405][405],p[405][405];



void init(){

    p[0][0]=1;

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

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

        

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

    }

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

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

    }

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

        p[i][0]=1;

        sm[i][0]=1;

        for(long long j=1;j<=400;++j){

            p[i][j]=(p[i][j-1]*i)%clz;

        }

    }

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

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

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

        }

    }

    memset(f,0,sizeof(f));

    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){

                long long t=(sm[b[i]][k]-sm[a[i]-1][k]+clz)%clz;

                f[i][j]=(f[i][j]+f[i-1][j-k]*t)%clz;

            }

        }

    }

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

}



int main(){

    init();

    return 0;

}

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



const int mod = 1e9 + 7; 

const int MaxN = 4e2 + 5; 



int n, c; 

int l[MaxN], r[MaxN]; 

int f[MaxN][MaxN], pw[MaxN][MaxN]; 



inline void add(int &x, const int &y)

{

	x += y; 

	(x >= mod) ? (x -= mod) : 0; 

}



int main()

{

//	freopen("candy.in", "r", stdin); 

//	freopen("candy.out", "w", stdout); 

	

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

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

		scanf("%d", l + i); 

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

		scanf("%d", r + i); 

	

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

		for (int j = l[i]; j <= r[i]; ++j)

		{

			int now = 1; 

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

			{

				add(pw[i][k], now); 

				now = 1LL * now * j % mod; 

			}

		}

	

	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)

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

	

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

	

	fclose(stdin); 

	fclose(stdout); 

	return 0; 

}

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



using namespace std ; 



#define N 500

#define ll long long

const ll mod = 1e9+7 ; 



ll n , m ;

ll a[ N ] , b[ N ] ;

ll sum[ N ][ N ] , l[ N ][ N ] ;

ll f[ N ][ N ] ;

//f[ i ][ j ]前i个人一共分了j个糖果 

//l[ i ][ j ]储存i的j次方

//sum[ i ][ j ]对l维护前缀和 



int main() {

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

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

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

    }

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

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

    }

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

        l[ i ][ 0 ] = 1 ;

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

            l[ i ][ j ] = l[ i ][ j - 1 ] * i  ;

            l[ i ][ j ] %= mod ;

        }

    }

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

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

            sum[ i ][ j ] += sum[ i - 1 ][ j ] + l[ i ][ j ] ;

            sum[ i ][ j ] %= mod ;

        }

    } 

    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 ] = ( f[ i ][ j ] % mod + ( 1ll * f[ i - 1 ][ j - k ] *( ( sum[ b[ i ] ][ k ] - sum[ a[ i ] - 1 ][ k ] ) % mod )  + mod ) % mod + mod ) % mod  ;

            }

        } 

    } 

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

    return 0 ;

} 

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



const int mod = 1e9 + 7; 

const int MaxN = 4e2 + 5; 



int n, c; 

int l[MaxN], r[MaxN]; 

int f[MaxN][MaxN], pw[MaxN][MaxN]; 



inline void add(int &x, const int &y)

{

	x += y; 

	(x >= mod) ? (x -= mod) : 0; 

}



int main()

{

//	freopen("candy.in", "r", stdin); 

//	freopen("candy.out", "w", stdout); 

	

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

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

		scanf("%d", l + i); 

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

		scanf("%d", r + i); 

	

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

		for (int j = l[i]; j <= r[i]; ++j)

		{

			int now = 1; 

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

			{

				add(pw[i][k], now); 

				now = 1LL * now * j % mod; 

			}

		}

	

	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)

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

	

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

	

	fclose(stdin); 

	fclose(stdout); 

	return 0; 

}

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

#define mod 1000000007

using namespace std;

int n,c,a[405],b[405],q[405][405],s[405][405],f[405][405],ans,mx;

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;

}

int main(){

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

		q[i][0]=1;

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

	}

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

		s[i][0]=1;

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

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

	}

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

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

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

	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)

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

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

} 

//记s[i][j]为1-j所有数的i次方之和 

//记f[i][j]为前i个人分j个糖果的答案，对于f[i][j]，可以从f[i-1][k](0<=k<=j)转移，给i个人j-k个糖果， 

//f[i][j]+=f[i-1][k]*(s[j-k][b[i]]-s[j-k][a[i]-1]) 

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

#include <cstring>

#include <algorithm>

#define R register

using namespace std;

const int mod=1000000007;

const int MAXN=410;

int a[MAXN],b[MAXN],po[MAXN][MAXN];

int dp[MAXN][MAXN];



int add(int x,int y)

{return (x+y)%mod;}

int sub(int x,int y)

{return (x-y+mod)%mod;}

int mul(int x,int y)

{return 1LL*x*y%mod;}



int main()

{

	int n,m;

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

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

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

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

	{

		int t=1;

		po[i][0]=i;

		for(R int j=1;j<=m;++j)

		{

			t=mul(t,i);

			po[i][j]=add(po[i-1][j],t);

		}

	}

	dp[0][0]=1;

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

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

		for(R int k=0;k<=m;++k)

		{

			if(j+k>m)break;

			dp[i][k+j]=add(dp[i][k+j],mul(dp[i-1][k],sub(po[b[i]][j],po[a[i]-1][j])));

		}

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

	return 0;

}

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

#include <cstring>

#include <algorithm>

#define mod 1000000007

#define MN 405

using namespace std;

int sum[MN][MN],pro[MN][MN],f[MN][MN],a[MN],b[MN];

int n,m;



inline int read()

{

	int n=0,f=1; char c=getchar();

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

	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}

	return n*f;

}



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



int main()

{

	register int i,j,k;

	n=read(); m=read();

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

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

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

		for (pro[i][0]=j=1;j<MN;++j)

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

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

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

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

				rw(sum[i][k],pro[j][k]);

	f[0][0]=1;

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

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

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

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

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

}

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

#include<algorithm>

#define MAXN 406

#define MOD 1000000007

using namespace std;

long long d[MAXN][MAXN];

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

long long ksm(long long a,int m)

{

	if(m==0) return 1;

	long long nex=ksm(a,m/2);

	nex=nex*nex%MOD;

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

	return nex*a%MOD;

}

int main()

{

	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]);

	d[0][0]=1;

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

	{

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

		{

			long long sum=0;

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

				sum=(sum+ksm(1ll*k,j))%MOD;

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

				d[i][l]=(d[i][l]+d[i-1][l-j]*sum)%MOD;

		}

	}

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

}

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

#define mod 1000000007

using namespace std;

int n,c,a[405],b[405],q[405][405],s[405][405],f[405][405],ans;

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;

}

int main(){

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

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

		q[i][0]=1;

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

	}

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

		s[i][0]=1;

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

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

	}

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

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

	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)

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

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

}

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

#include<algorithm>

#define MAXN 406

#define MOD 1000000007

using namespace std;

long long d[MAXN][MAXN];

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

long long ksm(long long a,int m)

{

	if(m==0) return 1;

	long long nex=ksm(a,m/2);

	nex=nex*nex%MOD;

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

	return nex*a%MOD;

}

int main()

{

	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]);

	d[0][0]=1;

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

	{

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

		{

			long long sum=0;

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

				sum=(sum+ksm(1ll*k,j))%MOD;

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

				d[i][l]=(d[i][l]+d[i-1][l-j]*sum)%MOD;

		}

	}

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

}

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

using namespace std;

const long long Mod=1e9+7;

int n,c,l[405],r[405];

long long G[405][405],f[405][405],a[405][405];

int main()

{

	//freopen("candies.in","r",stdin);

	//freopen("candies.out","w",stdout);

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

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

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

	for(long long i=1;i<=400;i++){G[i][0]=1;for(int j=1;j<=400;j++) G[i][j]=(G[i][j-1]*i)%Mod;}

	for(int i=1;i<=n;i++) for(int j=0;j<=c;j++) for(int u=l[i];u<=r[i];u++) f[i][j]=(f[i][j]+G[u][j])%Mod;

	a[0][0]=1;

	for(int i=1;i<=n;i++) for(int j=0;j<=c;j++) for(int k=0;k<=j;k++) a[i][j]=(a[i][j]+a[i-1][j-k]*f[i][k])%Mod;

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

}

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

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

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

int n,c;

const long long mod=1e9+7;

int A[405],B[405];

long long matmod(long long val,long long k){

	long long ret=1;

	for(;k;k>>=1){

		if(k&1) ret=(val*ret)%mod;

		val=(val*val)%mod;

	}

	return ret;

}

void add(long long &des,long long sor){des+=sor;des%=mod;return ;}

long long sum[405][405],f[405][405];

int main(){

	//freopen("candies.in","r",stdin);

	//freopen("candies.out","w",stdout);

	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 i=0;i<=c;i++){

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

			add(sum[i][j],sum[i][j-1]+matmod(j*1ll,i*1ll));

	}

	f[0][0]=1;

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

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

			for(int k=j;k>=0;k--)

				add(f[i][j],f[i-1][j-k]*(sum[k][B[i]]-sum[k][A[i]-1]+mod)%mod);

	}

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

	return 0;

}

// Fastest known solution for this problem: