#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int mod=100000007;
int dp[(1<<19)][19][19];
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>a(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=m;k++){
                dp[i][j][k]=0;
            }
        }
    }
    dp[0][m][0]=1;
    auto get_lca=[&m](int a,int b)->int{
        int ans=0;
        for(int i=m-1;i>=0;i--){
            if((a>>i)^(b>>i)){
                break;
            }
            ans++;
        }
        return ans;
    };
    for(int i=1;i<=n;i++){
        for(int j=a[i].first;j<=a[i].second;j++){
            int k1=get_lca(j,a[i].second);
            int k2=m;
            if(i!=n)
                k2=get_lca(j,a[i+1].first);
            int k3=get_lca(j,a[i].first);
            int k4=m;
            if(i!=n)
                k4=get_lca(j,a[i-1].second);
            for(int k=0;k<=m;k++){
                for(int o=0;o<=m;o++){
                    if(k4<=k&&k3>=o){
                        dp[i][k1][k2]=(dp[i][k1][k2]+dp[i-1][k][o]*j%mod)%mod;
                    }
                }
            }
        }
    }
    int re=0;
    for(int i=0;i<=m;i++){
        re=(re+dp[n][i][m])%mod;
    }
    cout<<re<<'\n';
}
signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin >> T;
    while(T--) solve();
    return 0;
}