#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int long long

const ll mod = 1e9 + 7;

struct Matrix {
    int n, m;
    vector<vector<ll>> a;

    void build(int n, int m) {
        a.assign(n + 1, vector<ll>(m + 1, 0));
        this->n = n, this->m = m;
    }

    void I() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                a[i][j] = 0;
            }
            a[i][i] = 1;
        }
    }

    Matrix Multi(Matrix mtx) {
        int n = this->n, m = mtx.m;
        int mid = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                for(int k = 1; k <= mid; k++) {
                    ans.a[i][j] += this->a[i][k] * mtx.a[k][j] % mod;
                    ans.a[i][j] %= mod;
                }
            }
        }
        return ans;
    }

    Matrix Add(Matrix mtx) {
        int n = this->n, m = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                // cout << i << ' ' << j << endl;
                ans.a[i][j] = (this->a[i][j] + mtx.a[i][j]) % mod;
            }
        }
        // ans.print();
        return ans;
    }

    Matrix Sub(Matrix mtx) {
        int n = this->n, m = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                ans.a[i][j] = (this->a[i][j] - mtx.a[i][j] + mod) % mod;
            }
        }
        return ans;
    }

    void print() {
        cout << n << ' ' << m << endl;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cout << a[i][j] << ' ';
            }
            cout << endl;
        }
    }

    void Clear() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                a[i][j] = 0;
            }
        }
    }
};

int n, m;
ll l, r;

Matrix A, B, W, w[70], s[70];

void pre() {
    w[0] = W;
    s[0] = W;
    for (int i = 1; i <= 60; i ++) {
        w[i] = w[i - 1].Multi(w[i - 1]);
        s[i] = s[i - 1].Add(s[i - 1].Multi(w[i - 1]));
    }
}

void init() {
    cin >> n >> m >> l >> r;
    W.build(n, n);
    B.build(n, n);
    for (int i = 1; i <= m; i ++) {
        ll u, v, w;
        cin >> u >> v >> w;
        if (v > n) {
            B.a[u][v - n] = w;
        } else {
            W.a[u][v] = w;
        }
    }
    A.build(n, n);
    A.I();
    auto tmp = W;

//  W.print();
    for (int i = 1; i <= n; i ++) {
        A = A.Add(W);
        W = W.Multi(tmp);
    }
    W = B.Multi(A);

//  A.print();
//  B.print();
//  W.print();
}

ll cal (ll x) {
//  cout << "cal: " << x << " *********************\n";
    if (x == 0) return 0;
    if (x <= n) {
        Matrix res, res2;
        res.build(1, n);
        res.a[1][1] = 1;
        res = res.Multi(A);
        res2 = res.Multi(W);
        ll ans = 0;
        for (int i = 1; i <= x; i ++) {
            if (i <= n) ans = (ans + res.a[1][i]) % mod;
            else ans = (ans + res2.a[1][i - n]) % mod;
        }
        return ans;
    }

    Matrix res;
    res.build(1, n);
    res.a[1][1] = 1;
    res = res.Multi(A);
    Matrix cur_w, cur_s;
    cur_w.build(n, n);  cur_w.I();
    cur_s.build(n, n);  cur_s.I();

    ll k = (x - 1) / n - 1;
    for (int i = 0; i <= 60; i ++) {
        if ((k >> i) & 1) {
            cur_s = cur_s.Add(s[i].Multi(cur_w));
            cur_w = cur_w.Multi(w[i]);
        }
    }
    ll ans = 0;
    auto res1 = res.Multi(cur_s);
    for (int i = 1; i <= n; i ++) {
        ans = (ans + res1.a[1][i]) % mod;
    }
    auto res2 = res.Multi(cur_w.Multi(W));
    x = (x - 1) % n + 1;
    for (int i = 1; i <= x; i ++) {
        ans = (ans + res2.a[1][i]) % mod;
    }
//  cout << "ans: " << ans << endl;
    return ans;
}


void solve() {
    init();
    pre();

    ll res1 = cal(l - 1), res2 = cal(r);
    cout << (res2 - res1 + mod) % mod << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}