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

#include<vector>

#include<queue>

#include<algorithm>

#include<functional>

#include<cmath>

using namespace std;

#define P pair<int,int>

int V,E;

struct edge{int to,cost;};

vector<edge>G[110000];

int ans[110000];

const int INF=pow(2,30);

int main(){

	fill(ans,ans+100000,INF);

	int r;

	cin>>V>>E>>r;

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

	int s,t,d;

	cin>>s>>t>>d;

	edge tmp;

	tmp.to=t,tmp.cost=d;

	G[s].push_back(tmp);

	}

	ans[r]=0;

	priority_queue<P,vector<P>,greater<P> >que;

	que.push(make_pair(0,r));//距離、番号

	while(true){

		if(que.size()==0)break;

		//for(int i=0;i<V;i++)cout<<ans[i]<<" ";cout<<" ";

		P tmp=que.top();//ここで使われていないものの中で最も距離が小さい頂点vの番号を求める

		que.pop();

		//cout<<tmp.first<<" "<<tmp.second<<endl;

		int v=tmp.second;

		//if(ans[v]<tmp.first)cout<<ans[v]<<" "<<tmp.first<<" "<<tmp.second<<endl;;

		if(ans[v]<tmp.first)continue;

		for(int i=0;i<G[v].size();i++){

			if(ans[G[v][i].to]>ans[v]+G[v][i].cost){

			ans[G[v][i].to]=ans[v]+G[v][i].cost;

			que.push(P(ans[G[v][i].to],G[v][i].to));

			}

		}

	}

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

	if(ans[i]==INF)cout<<"INF"<<endl;

	else cout<<ans[i]<<endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1008976897718852x):
#include<algorithm>//sort,二分探索,など

#include<bitset>//固定長bit集合

#include<cmath>//pow,logなど

#include<complex>//複素数

#include<deque>//両端アクセスのキュー

#include<functional>//sortのgreater

#include<iomanip>//setprecision(浮動小数点の出力の誤差)

#include<iostream>//入出力

#include<map>//map(辞書)

#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)

#include<queue>//キュー

#include<set>//集合

#include<stack>//スタック

#include<string>//文字列

#include<utility>//pair

#include<list>

#include<vector>//可変長配列

using namespace std;

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

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

#define mp make_pair

#define pb push_back

#define ll __int64

#define __int64 long long

#define P pair<int,int>

#define PP pair<ll,ll>

#define F first

#define S second

int dx[8] = { 1,0,-1,0,1,-1,-1,1 };

int dy[8] = { 0,1,0,-1,1,1,-1,-1 };



int n, m, r;

ll dist[111111];

const ll INF = 1e13;

vector<P>G[111111];



int main() {

	cin >> n >> m >> r;

	rep(i, m) {

		int a, b, c;

		cin >> a >> b >> c;

		G[a].pb(mp(b, c));

	}



	priority_queue<PP, vector<PP>, greater<PP> >bfs;



	rep(i, n)dist[i] = INF;

	bfs.push(mp(0, r));



	while (!bfs.empty()) {

		ll d = bfs.top().first, from = bfs.top().second;

		bfs.pop();

		if (dist[from] != INF)

			continue;



		dist[from] = d;

		for (int i = 0; i < G[from].size(); i++) {

			ll to = G[from][i].first, next_cost = d+G[from][i].second;

			bfs.push(mp(next_cost, to));

		}

	}

	rep(i, n) {

		if (dist[i] == INF)cout << "INF" << endl;

		else cout << dist[i] << endl;

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define fi first

#define se second



const int MAXN = 100000;



typedef pair<int, int> ii;

typedef vector<ii> vii;



vii adjList[MAXN];



int dist[MAXN]; bitset<MAXN> inq;

queue<int> q;



int main(){



    int N, E, S;

    cin >> N >> E >> S;



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

        int s, t, d;

        cin >> s >> t >> d;



        adjList[s].push_back(ii(d,t));

    }



    memset(dist, -1, sizeof(dist)); dist[S] = 0;

    inq.reset(); inq[S] = 1;

    

    q.push(S);

    while (!q.empty()) {

        int x = q.front(); q.pop();

        

        inq[x] = 0;

        for (vii::iterator it = adjList[x].begin(); it != adjList[x].end(); ++it) {

            int nn = it->se;

            int nd = dist[x]+it->fi;



            if (dist[nn] != -1 && dist[nn] <= nd) continue;

            

            dist[nn] = nd;

            if (!inq[nn]) q.push(nn);

            inq[nn] = 1;

        }

    }



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

        if (dist[i] == -1) cout << "INF" << endl;

        else cout << dist[i] << endl;

    }

}

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

using namespace std;



#define fi first

#define se second



typedef pair<int, int> ii;



const int MAXN = 100005;

const int INF = 1 << 30;

 

int V, E, S, d[MAXN];

vector<ii> adjList[MAXN];

 

int main() {



    scanf("%d%d%d",&V,&E,&S);

    for (int i = 0, u, v, w; i < E; i++) {

        scanf("%d%d%d",&u,&v,&w);



        adjList[u].push_back(ii(w,v));

      //adjList[v].push_back(ii(w,u));

    }

 

    fill(d,d+V,INF); d[S] = 0;

    priority_queue< ii,vector<ii>,greater<ii> > pq; pq.push(ii(0,S));

    while(!pq.empty()) {

        ii p = pq.top(); pq.pop();

        int dist = p.fi, u = p.se;

 

        if(dist > d[u]) continue;

 

        for (int i = 0; i < adjList[u].size(); i++) {

            ii &v = adjList[u][i];

 

            if (d[v.se] > d[u] + v.fi) {

                d[v.se] = d[u] + v.fi;

                pq.push(ii(d[v.se], v.se));

            }

        }

    }

 

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

        if (d[i] == INF)

            puts("INF");

        else

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

 

    return 0;

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

#include <cstdio>





using namespace std;



const long int INF = 5000000000;

const int MAX_E = 500000;

const int MAX_V = 100000;



struct edge   //??????????????????cost???(from,to)??¨??????(?????????)???

{

	int from;

	int to;

	int cost;



	edge()

	{

		from = 0;

		to = 0;

		cost = 0;

	}

};



//edge es[MAX_E];



int V,E,r;    //??°?????????????????°,?????°,?§????

long int d[MAX_V];

edge es[MAX_E];







void shortest_path(int r)

{

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

	{

		d[i] = INF;

	}



	d[r] = 0;



	while(true)

	{

		bool update = false;



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

		{

			edge e = es[i];



			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost)

			{

				d[e.to] = d[e.from] + e.cost;

				update = true;

			}

		}



		if (!update) break;

	}

}





int main()

{

	int a[10];

	//edge es[MAX_E];



	scanf(" %d %d %d", &V,&E,&r);



	//cout << endl;

	//cout << V << E << r << endl;





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

	{

		scanf(" %d %d %d", &es[i].from, &es[i].to, &es[i].cost);

	}



	/*for(int i = 0; i < E; i++)

	{

		//scanf("%d %d %d", &es[i].from, &es[i].to, &es[i].cost);

		printf("%d %d", i,es[i].from);

		printf(" %d", es[i].to);

		printf(" %d", es[i].cost);

		cout << endl;

	}





	cout << "okok";*/



	shortest_path(r);



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

	{

		if (d[i] == INF)

		{

			printf("INF\n");

		}else

		{

			printf("%ld\n", d[i]);

		}

	}



	return 0;

}

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

#include <string>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <queue>

#include <set>

#include <numeric>



using namespace std;



typedef long long int lld;

typedef pair<lld,lld> P;



const lld mod = 1e9+7;

const lld INF = 1e9;

const lld MAXE = 500000;

const lld MAXV = 100000;



struct edge

{

	lld to,cost;

};



int main()

{

	lld V,E,r;

	vector<edge> e[MAXV];



	cin >> V >> E >> r;

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

	{

		lld s,t,d;

		cin >> s >> t >> d;

		

		edge ee;

		ee.to = t, ee.cost = d;

		e[s].push_back(ee);

	}



	lld dist[MAXV];

	fill(dist,dist+V,INF);

	dist[r] = 0;



	priority_queue< P, vector<P>, greater<P> > Q;



	Q.push(P(0,r));



	while(!Q.empty())

	{

		//printf("okok\n");

		P p = Q.top();

		Q.pop();



		lld v = p.second;

		if (dist[v] < p.first)

		{

			continue;

		}



		for(int i = 0; i < e[v].size(); i++)

		{

			//printf("bbbb\n");

			edge ee = e[v][i];

			//printf("ee.cost = %lld\n",ee.cost);

			//printf("dist[ee.to] = %lld\n", dist[ee.to]);

			if (dist[ee.to] > dist[v] + ee.cost)

			{

				dist[ee.to] = dist[v] + ee.cost;



				//printf("dist[%lld] = %lld\n", ee.to,dist[ee.to]);



				Q.push(P(dist[ee.to],ee.to));

			}

		}

	}



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

	{

		if (dist[i] == INF)

		{

			cout << "INF" << endl;

		}else

		{

			cout << dist[i] << endl;

		}

	}



	return 0;

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

#include <algorithm>

#include <map>

#include <vector>

using namespace std;

typedef long long ll;

#define INF 2147483647



struct edge{

    int to,cost;

};

int V,E; 



vector <edge> G[100010];



multimap <int,int> l;





ll d[500010];





void dijkstra(int s){

    fill(d,d+V,INF);

    d[s] = 0;



    l.insert(make_pair(0,s));



    while(l.size() > 0){

        int p = l.begin()->first;

        int v = l.begin()->second;

        l.erase(l.begin());



        if(d[v] < p) continue;



        for(int i = 0;i < G[v].size(); i++){

            edge e = G[v][i];

            if(d[e.to] > d[v] + e.cost){

                d[e.to] = d[v] + e.cost;

                l.insert(make_pair(d[e.to], e.to));

            }

        }

    }

}





int main(){



    int r;

    cin >> V >> E >> r;

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

         edge e;

        int from;

        cin >> from >> e.to >> e.cost;

        G[from].push_back(e);

    }



    dijkstra(r);



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

        if(d[i] != INF) cout << d[i] << endl;

        else cout << "INF" <<endl;

    }

    return 0;

} 

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

#include <queue>

#include <algorithm>

#include <utility>



using namespace std;



const int Inf = 10000*100000+100;

int a,b,V,E,R,S,Start[500000+10],To[500000+10],Dis[500000+10],N[500000+10];

int Ans[100000+10];



priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;





int main() {

	cin >> V >> E >> R;

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

		cin >> S >> To[i] >> Dis[i];

		N[i] = Start[S];

		Start[S] = i;

	}

	

	fill(Ans,Ans+100010,Inf);

	Ans[R] = 0;

	Q.push(make_pair(0,R));

	

	while(!Q.empty()){

		a = Q.top().first;

		b = Q.top().second;

		Q.pop();

		if (Ans[b] == a){

			for(int i=Start[b]; i; i=N[i]){

				int t = To[i];

				if (a+Dis[i] < Ans[t]){

					Ans[t] = a+Dis[i];

					Q.push(make_pair(Ans[t],t));

				}

			}

		}	

	}

	

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

		if (Ans[i] < Inf){

			cout << Ans[i] << endl;

		}else{

			cout << "INF" << endl;

		}

	}	

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define vi vector<ll>

#define vvi vector<vi>

#define BITLE(n) (1LL<<(n))

#define BITCNT(n) (__builtin_popcountll(n))

#define SUBS(s,f,t) (s.substr(f-1,t-f+1))

#define ALL(a) (a).begin(),(a).end()



using namespace std;

struct Grid{ll x,y,t;};

struct Edge{ll to,cost;};

struct Graph{vector<vector<Edge>>E;int V;

  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;

  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}

  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}

  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}

};

vi hog(100010);

int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  ll a,b,c,d,e;

  string s,ss,sss;

  cin>>a>>b;

  if((a+1)/2>=b)

  cout<<"YES"<<endl;

  else

    cout<<"NO"<<endl;

  return 0;

}


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

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define vi vector<ll>

#define vvi vector<vi>

#define BITLE(n) (1LL<<((ll)n))

#define SHIFT_LEFT(n) (1LL<<((ll)n))

#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))

#define ALL(a) (a).begin(),(a).end()

using namespace std;

struct UF

{

  vector<int> par;

  vector<int> sz;

  vector<int> rank;

  UF(int n):par(n),sz(n),rank(n){

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

      par[i] = i;sz[i] = 1;rank[i] = 0;

    }

  }

  int find(int x) {

    if (par[x] == x) return x;

    else return par[x] = find(par[x]);

  }

  void merge(int x, int y) {

    x = find(x); y = find(y);

    if (x == y) return;

    if(rank[x] < rank[y]){

      par[x] = y;

      sz[y] += sz[x];

    }

    else{

      par[y] = x;

      sz[x] += sz[y];

      if(rank[x] == rank[y])rank[x]++;

    }

  }

  bool same(int x, int y) { return find(x) == find(y); }

  int size(int n){return sz[find(n)];}

};



bool isdig(char c){

  return '0' <= c && c <= '9';

}



int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  ll a,b;cin>>a>>b;

  if(a%2){

    a++;

    if(a/2 >= b){

      cout<<"YES"<<endl;

    }else{

      cout<<"NO"<<endl;

    }

  }else{

    if(a/2 >= b){

      cout<<"YES"<<endl;

    }else{

      cout<<"NO"<<endl;

    }

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long LL;



const LL MOD = 1e9+7;



inline LL dmod(LL x){

	return x%MOD;

}



int n,c;



LL pang[405][405];

LL ps[405][405];



void pre(){

	for(int i=0;i<=400;i++) pang[i][0] = 1LL;

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

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

			pang[i][j] = dmod(pang[i][j-1]*(LL)i);

		}

	}

	for(int i=0;i<=400;i++) ps[0][i] = pang[0][i];

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

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

			ps[i][j] = dmod(ps[i-1][j] + pang[i][j]);

		}

	}

}



//int n,c;

int A[405],B[405];



LL memo[405][405];



LL dp(int id, int sisa){

	if(id > n){

		if(sisa == 0) return 1LL;

		else return 0LL;

	}

	LL &ret = memo[id][sisa];

	if(ret!=-1) return ret;

	ret = 0LL;

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

		ret = dmod(ret+dmod(dp(id+1,sisa-i)*dmod(ps[B[id]][i] - ps[A[id]][i]+MOD)));

	}

	return ret;

}



int main(){

	pre();

//	for(int i=0;i<=5;i++){

//		for(int j=0;j<=5;j++){

//			cout << ps[i][j] << " ";

//		}

//		cout << endl;

//	}

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

	cin >> n >> c;

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

		cin >> A[i];

		A[i]--;

	}

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

		cin >> B[i];

	}

	LL ans = dp(1,c);

	cout << ans << endl;

	return 0;

}

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

  mail: mleautomaton@foxmail.com

  author: MLEAutoMaton

  This Code is made by MLEAutoMaton

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define int ll

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

inline int gi(){

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

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

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

	return f*sum;

}

const int N=410,Mod=1e9+7;

int a[N],b[N],n,sum[N][N],c,dp[N][N];

int val(int i,int Q){

	return (sum[Q][b[i]]-sum[Q][a[i]-1]+Mod)%Mod;

}

int qpow(int a,int b){

	int ret=1;

	while(b){

		if(b&1)ret=1ll*ret*a%Mod;b>>=1;

		a=1ll*a*a%Mod;

	}

	return ret;

}

signed main(){

	n=gi();c=gi();

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

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

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

			sum[i][j]=(sum[i][j-1]+qpow(j,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]+1ll*dp[i-1][k]*val(i,j-k)%Mod)%Mod;

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long LL;



const LL MOD = 1e9+7;



inline LL dmod(LL x){

	return x%MOD;

}



int n,c;



LL pang[405][405];

LL ps[405][405];



void pre(){

	for(int i=0;i<=400;i++) pang[i][0] = 1LL;

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

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

			pang[i][j] = dmod(pang[i][j-1]*(LL)i);

		}

	}

	for(int i=0;i<=400;i++) ps[0][i] = pang[0][i];

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

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

			ps[i][j] = dmod(ps[i-1][j] + pang[i][j]);

		}

	}

}



//int n,c;

int A[405],B[405];



LL memo[405][405];



LL dp(int id, int sisa){

	if(id > n){

		if(sisa == 0) return 1LL;

		else return 0LL;

	}

	LL &ret = memo[id][sisa];

	if(ret!=-1) return ret;

	ret = 0LL;

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

		ret = dmod(ret+dmod(dp(id+1,sisa-i)*dmod(ps[B[id]][i] - ps[A[id]][i]+MOD)));

	}

	return ret;

}



int main(){

	pre();

//	for(int i=0;i<=5;i++){

//		for(int j=0;j<=5;j++){

//			cout << ps[i][j] << " ";

//		}

//		cout << endl;

//	}

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

	cin >> n >> c;

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

		cin >> A[i];

		A[i]--;

	}

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

		cin >> B[i];

	}

	LL ans = dp(1,c);

	cout << ans << endl;

	return 0;

}

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

#include <cstdio>

#include <cstring>

#define int long long

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;



inline int read(){

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

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

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

	return f*sum;

}



const int N=405;

const int Mod=1000000007;

struct node{int l,r;}a[N];

int n,C,f[N][N],p[N];



signed main(){

	n=read();C=read();

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

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

	f[0][0]=1;

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

		for(int i=0;i<N;i++) p[i]=0;

		for(int x=a[i].l;x<=a[i].r;x++){

			int ret=1;p[0]++;

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

				ret=ret*x%Mod;p[j]=(p[j]+ret)%Mod;

			}

		}

		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]*p[k]%Mod)%Mod;

			}

		}

	}

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;

#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)

#define REP(i,a,b) REPP(i,a,b,1)

#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)

#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) REP(i,0,(int)a-1)

#define FORD(i,a) REV(i,(int)a-1,0)

#define PB push_back

#define POB pop_back

#define FI first

#define SE second

#define MP make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair < int , int > pii;

typedef vector < int > vi;

typedef vector < pii > vii;

typedef vector < ll > vl;

typedef pair < ll , ll > pll;



const double PI = acos(-1);

const double EPS = 1e-9;

const ll MOD = 1e9 + 7;

const int INF = 1e9;

	



ll addMod(ll a, ll b){

	if(a + b >= MOD) return a + b - MOD;

	return a + b;

}



ll mulMod(ll a, ll b){

	return (a*b)%MOD;

}



ll fast(ll a, ll b){

	if(b == 0) return 1;

	ll tmp = fast(a,b/2);

	tmp = mulMod(tmp,tmp);

	if(b%2 == 1) tmp = mulMod(tmp,a);

	return tmp;

}



ll GCD(ll a, ll b){

	if(a > b) return GCD(b,a);

	if(a == 0) return b;

	return GCD(b%a,a);

}



//////////////////////////////////////////////



const int N = 400;



int n,m;

ll dp[N + 5][N + 5];

ll tot[N + 5][N + 5];

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



ll solve(int idx, int rem){

	if(idx == n+1){

		if(rem == 0) return 1;

		return 0;

	}

	ll& ret = dp[idx][rem];

	if(ret != -1) return ret;

	ret = 0;

	FOR(i,rem+1){

		ret = addMod(ret, mulMod(solve(idx+1,rem-i), addMod(tot[i][B[idx]], MOD - tot[i][A[idx]-1])));

	}

	return ret;

	

}

int main(){

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

	FOR(i,N+2){

		FOR(j,N+2){

			tot[i][j] = (i == 0) ? 1 : mulMod(tot[i-1][j], (ll)j);

		}

	}

	FOR(i,N+2){

		tot[i][0] = 0;

		REP(j,1,N){

			tot[i][j] = addMod(tot[i][j], tot[i][j-1]);

		}

	}

	cin >> n >> m;

	REP(i,1,n) cin >> A[i];

	REP(i,1,n) cin >> B[i];

	memset(dp,-1,sizeof dp);

	cout << solve(1,m) << endl;

	return 0;

}

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

#include <cstdio>

#include <cstring>

#define int long long

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;



inline int read(){

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

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

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

	return f*sum;

}



const int N=405;

const int Mod=1000000007;

struct node{int l,r;}a[N];

int n,C,f[N][N],p[N];



signed main(){

	n=read();C=read();

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

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

	f[0][0]=1;

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

		for(int i=0;i<N;i++) p[i]=0;

		for(int x=a[i].l;x<=a[i].r;x++){

			int ret=1;p[0]++;

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

				ret=ret*x%Mod;p[j]=(p[j]+ret)%Mod;

			}

		}

		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]*p[k]%Mod)%Mod;

			}

		}

	}

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

	return 0;

}
// Slower C++ solution:
/*

  mail: mleautomaton@foxmail.com

  author: MLEAutoMaton

  This Code is made by MLEAutoMaton

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define int ll

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

inline int gi(){

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

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

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

	return f*sum;

}

const int N=410,Mod=1e9+7;

int a[N],b[N],n,sum[N][N],c,dp[N][N];

int val(int i,int Q){

	return (sum[Q][b[i]]-sum[Q][a[i]-1]+Mod)%Mod;

}

int qpow(int a,int b){

	int ret=1;

	while(b){

		if(b&1)ret=1ll*ret*a%Mod;b>>=1;

		a=1ll*a*a%Mod;

	}

	return ret;

}

signed main(){

	n=gi();c=gi();

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

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

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

			sum[i][j]=(sum[i][j-1]+qpow(j,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]+1ll*dp[i-1][k]*val(i,j-k)%Mod)%Mod;

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

	return 0;

}


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

#include <cstdio>

#include <cstring>

#define int long long

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;



inline int read(){

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

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

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

	return f*sum;

}



const int N=405;

const int Mod=1000000007;

struct node{int l,r;}a[N];

int n,C,f[N][N],p[N];



signed main(){

	n=read();C=read();

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

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

	f[0][0]=1;

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

		for(int i=0;i<N;i++) p[i]=0;

		for(int x=a[i].l;x<=a[i].r;x++){

			int ret=1;p[0]++;

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

				ret=ret*x%Mod;p[j]=(p[j]+ret)%Mod;

			}

		}

		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]*p[k]%Mod)%Mod;

			}

		}

	}

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

	return 0;

}