#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<array<int,3>,3> S;
const int N=1e4,inf=1e9,K=100,mod=1e9+7;
map<S,int> id;
int g[N][5],tot,f[N],nf[N],n,m;
S to[N];
void u1(int &x,int y){x=min(x,y);}
void u2(int &x,int y){x+=y,(x>=mod&&(x-=mod));}
void dfs(S f){
	int I=id[f];
	for(int v=0;v<=4;v++){
		S nf;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)nf[i][j]=inf;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<=i;k++){
					if(i+j-k>2)continue;
					for(int l=0;l<=2;l++){
						if(i+j-k==2&&l==2)continue;
						int nv=i+j+l;
						for(int tov=max(nv,v);tov<=v+2;tov++){
							if(nv==tov-1)continue;
							u1(nf[i+j-k][l],f[i][j]+tov-v);
						}
					}
				}
			}
		}
		bool bad=1;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(nf[i][j]<=K)bad=0;
		if(bad)continue;
		if(!id.count(nf))id[nf]=++tot,to[tot]=nf,dfs(nf);
		g[I][v]=id[nf];
	}
}
void Solve(){
	scanf("%d%d",&n,&m),memset(f,0,sizeof(f)),f[1]=1;
	bool all0=1,all1=1;
	for(int i=1,l,r;i<=n+1;i++){
		if(i<=n)scanf("%d%d",&l,&r);
		else l=r=0;
		memset(nf,0,sizeof(nf));
		for(int j=1;j<=tot;j++){
			if(!f[j])continue;
			for(int k=max(l,0),rk=min(r,3);k<=rk;k++)
				u2(nf[g[j][k]],f[j]);
			u2(nf[g[j][4]],1ll*f[j]*max(0,r-max(l,4)+1)%mod);
		}
		if(i<=n)all0&=(l==0),all1&=(l<=1&&r>=1);
		memcpy(f,nf,sizeof(f));
	}
	int ans=0;
	for(int i=1;i<=tot;i++){
		S tf=to[i];
		if(tf[0][0]<=m)u2(ans,f[i]);
	}
	if(m==1){
		if(all0)ans=(ans-1+mod)%mod;
		if(all1&&n==3)ans=(ans-1+mod)%mod;
	}
	cout<<ans<<'\n';
}
int main(){
	S fr;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)fr[i][j]=inf;
	fr[0][0]=0,id[fr]=++tot,to[tot]=fr;
	dfs(fr);
	int t;
	scanf("%d",&t);
	while(t--)Solve();
}