#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define ll long long
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^'0');
		ch=getchar();
	}
	return x;
}
int num_[50],cnt_;
inline void write(int x){
	if(x==0){
		putchar('0');
		return;
	}
	while(x){
		num_[++cnt_]=x%10;
		x/=10;
	}
	while(cnt_)putchar(num_[cnt_--]+'0');
}
int n,k,l[1002],r[1002];
#define mod 1000000007
const int K=3;
struct S{
	int f[3][3];
	inline S upd(int v){
		S nxt;
		F(i,0,2)F(j,0,2)nxt.f[i][j]=k+1;
		F(i,0,2)F(j,0,min(2,K-i)){
			F(d,max(0,i+j-2),i){
				F(u,0,min(2,K-i-j)){
					nxt.f[i+j-d][u]=min(nxt.f[i+j-d][u],f[i][j]+max(i+j+u-v,int(i+j+u==v-1)));
				}
			}
		}
		return nxt;
	}
};
inline bool operator<(const S &x,const S &y){
	return memcmp(x.f,y.f,9<<2)<0;
}
inline int check(){
	if(n>=4)return k==1&&(*max_element(l+1,l+n+1))<=0;
	bool flag1=false,flag2=false;
	F(i,1,n)if(l[i]>1||r[i]<1)return k==1&&(*max_element(l+1,l+n+1))<=0;
	return int(k==1)+(k==1&&(*max_element(l+1,l+n+1))<=0);
}
map<S,int>id;
int cnt,trans[7156][6];
S to[7156];
int dp[1002][7156];
inline void bfs(){
	cnt=0;id.clear();
	S temp;F(i,0,2)F(j,0,2)temp.f[i][j]=k+1;temp.f[0][0]=0;
	id[temp]=++cnt;to[cnt]=temp;
	for(int i=1;i<=cnt;++i){
		F(j,0,5){
			S qwq=to[i].upd(j);
			if(id.count(qwq))trans[i][j]=id[qwq];
			else{
				trans[i][j]=id[qwq]=++cnt;
				to[cnt]=qwq;
			}
		}
	}
}
int main(){
//	freopen("stone.in","r",stdin);
//	freopen("stone.out","w",stdout);
	k=100;bfs();
	F(iakioi,1,read()){
		memset(dp,0,sizeof(dp));
		n=read(),k=read();
		F(i,1,n)l[i]=read(),r[i]=read();
		dp[0][1]=1;
		F(i,0,n-1){
			F(j,1,cnt){
				F(v,max(l[i+1],0),min(r[i+1],4))(dp[i+1][trans[j][v]]+=dp[i][j])%=mod;
				if(r[i+1]>4)dp[i+1][trans[j][5]]=(dp[i+1][trans[j][5]]+1ll*dp[i][j]*min(r[i+1]-l[i+1]+1,r[i+1]-4))%mod;
			}
		}
		ll ans=0;
		F(i,1,cnt)if(to[i].f[0][0]<=k)ans+=dp[n][i];
		ans+=mod-check();
		write(ans%mod);putchar('\n');
	}
	return 0;
}