#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64; 
const int N = 1e3 + 5; 
const int P = 1e9 + 7; 
const int M = 1e5 + 5; 

inline void add(int &x, int k) { x += k; x -= x >= P ? P : 0; }
inline void ckmin(int &x, int k) { x = x < k ? x : k; }

int n, m; 
int L[N], R[N]; 

struct Node {
    int f[3][3]; 
    Node() { memset(f, 0x3f, sizeof f); }
    bool win(void) { return f[0][0] <= m; }
    u64 enc(void) {
        u64 h = 0; 
        for (int i = 0; i < 3; ++i) 
            for (int j = 0; j < 3; ++j)
                h = h * 233 + f[i][j]; 
        return h; 
    }
} b[M]; 
unordered_map<u64, int> mp; 
int tot; 

int G[M][9]; 
void bfs(void) {
    Node I; I.f[0][0] = 0; b[++tot] = I; mp[I.enc()] = tot; 
    queue<int> q; q.push(1); 
    while (!q.empty()) {
        int id = q.front(); q.pop(); 
        Node fr = b[id]; 
        for (int i = 0; i <= 8; ++i) {
            Node to; 
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k) if (fr.f[j][k] <= 100) {
                    for (int l = 0; l < 3; ++l) {
                        int u = i - j - k - l; 
                        int v = u < 0 ? -u : u == 1 ? 1 : 0; 
                        for (int p = k; p <= j + k && p < 3; ++p)
                            ckmin(to.f[p][l], fr.f[j][k] + v); 
                    }
                }
            if (mp.find(to.enc()) == mp.end()) b[++tot] = to, mp[to.enc()] = tot, q.push(tot); 
            G[id][i] = mp[to.enc()]; 
        }
    }
}

int f[2][M]; 

void solve(void) {
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> L[i] >> R[i]; 
    memset(f, 0, sizeof f); f[0][1] = 1; 

    for (int i = 1; i <= n; ++i) {
        int o = i & 1; memset(f[o], 0, sizeof f[o]); 
        int l = L[i], r = min(R[i], 7); 
        for (int j = 1; j <= tot; ++j) if (f[o ^ 1][j]) {
            for (int k = l; k <= r; ++k) add(f[o][G[j][k]], f[o ^ 1][j]); 
            int v = max(0, R[i] - max(8, L[i]) + 1); 
            add(f[o][G[j][8]], 1ll * f[o ^ 1][j] * v % P); 
        }
    }
    int ans = 0; 
    for (int i = 1; i <= tot; ++i) if (b[i].win()) add(ans, f[n & 1][i]); 

    if (m == 1) {
        if (*max_element(L + 1, L + n + 1) == 0) --ans; 
        if (n == 3 && *max_element(L + 1, L + n + 1) <= 1 && *max_element(R + 1, R + n + 1) >= 1) --ans; 
    }
    cout << (ans + P) % P << "\n"; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    bfs(); 
    cerr << tot << "\n"; 
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}