#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) cout<<(#_v)<<":";for(auto(_x):(_v)){cout<<" "<<(_x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}
 
inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}
 
using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;
 
using Vec = vector<int>;
using Mat = vector<Vec>;
 
Mat mulMatMat(const Mat& a, const Mat& b) {
    int n = a.size();
    int m = b[0].size();
    assert(a[0].size() == b.size());
    Mat c(n, Vec(m, 0));
    rep(i, n) {
        rep(j, m) {
            rep(k, a[0].size()) {
                (c[i][j] += a[i][k] * b[k][j]) %= mod;
            }
        }
    }
    return c;
}
 
void addMatMat(Mat& a, const Mat& b) {
    assert(a.size() == b.size());
    assert(a[0].size() == b[0].size());
    rep(i, a.size()) {
        rep(j, a[0].size()) {
            (a[i][j] += b[i][j]) %= mod;
        }
    }
}
 
Vec mulMatVec(const Mat& a, const Vec& v) {
    int n = a.size();
    assert(a[0].size() == v.size());
    Vec c(n, 0);
    rep(i, n) {
        rep(j, a[0].size()) {
            (c[i] += a[i][j] * v[j]) %= mod;
        }
    }
    return c;
}
 
Mat identityMatrix(int n) {
    Mat a(n, Vec(n));
    rep(i, n) a[i][i] = 1;
    return a;
}
 
Mat powMat(Mat a, int t) {
    assert(a.size() == a[0].size());
    Mat b = identityMatrix(a.size());
    for (; t > 0; t >>= 1) {
        if (t & 1) {
            b = mulMatMat(a, b);
        }
        a = mulMatMat(a, a);
    }
    return b;
}
 
main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int N, K, C, T;
    cin >> N >> K >> C >> T;
    C--;
    vector<Mat> A(5, Mat(N, Vec(N)));
    rep(k, K) {
        int a, b, t;
        cin >> a >> b >> t;
        a--; t--;
        rep(i, a) A[t][i][i + b]++;
        rep2(i, a, a + b) A[t][i][i - a]++;
        rep2(i, a + b, N) A[t][i][i]++;
    }
 
    // rep(t, 5) {
    //     printVV(A[t]);
    // }
 
    Mat B(5*N, Vec(5*N));
    rep(t, 5) {
        rep(i, N) {
            rep(j, N) {
                B[i][j + t*N] = A[t][i][j];
            }
        }
    }
    rep(j, 4 * N) {
        B[j + N][j] = 1;
    }
 
    // printVV(B);
 
    vector<Mat> dp(5, Mat(N, Vec(N)));
    dp[0] = identityMatrix(N);
    rep2(i, 1, 5) {
        rep(j, i) {
            addMatMat(dp[i], mulMatMat(A[i - j - 1], dp[j]));
        }
    }
 
    // rep(t, 5) {
    //     printVV(dp[t]);
    // }
 
    auto D = powMat(B, T);
 
    Mat E(N, Vec(N));
    rep(k, 5) {
        Mat F(N, Vec(N));
        rep(i, N) {
            rep(j, N) {
                F[i][j] = D[i + 4*N][j + k*N];
            }
        }
        addMatMat(E, mulMatMat(F, dp[4 - k]));
    }
 
    cout << E[C][0] << endl;
}

Measured memory_bytes: 4212