#include <bits/stdc++.h>
#include <random>
using namespace std;

// ref: https://judge.yosupo.jp/submission/102040

template<int M> struct MINT {
    long long v;
    static MINT<M> w;
    MINT<M>() : v(0) {}
    MINT<M>(const long long v) : v(v) { normalize(); }
    void normalize() { v %= M; if (v < 0) v += M; }

    friend istream& operator >> (istream& in, MINT<M>& a) { in >> a.v; a.normalize(); return in; }
    friend ostream& operator << (ostream& out, const MINT<M>& a) { return out << a.v; }
    friend MINT<M> pow(MINT<M> a, long long b) {
        MINT<M> res = 1;
        for (; b; b >>= 1, a *= a) if (b & 1) res *= a;
        return res;
    }

    MINT<M> power(long long b) const { return pow(*this, b); }
    MINT<M> mul_inv() const { return power(M - 2); }

    MINT<M>& operator += (const MINT<M>& t) { if ((v += t.v) >= M) v -= M; return *this; }
    MINT<M>& operator -= (const MINT<M>& t) { if ((v -= t.v) < 0) v += M; return *this; }
    MINT<M>& operator *= (const MINT<M>& t) { v *= t.v; normalize(); return *this; }
    MINT<M>& operator /= (const MINT<M>& t) { *this *= t.mul_inv(); normalize(); return *this; }

    MINT<M> operator + (const MINT<M>& t) const { return MINT<M>(*this) += t; }
    MINT<M> operator - (const MINT<M>& t) const { return MINT<M>(*this) -= t; }
    MINT<M> operator * (const MINT<M>& t) const { return MINT<M>(*this) *= t; }
    MINT<M> operator / (const MINT<M>& t) const { return MINT<M>(*this) /= t; }
    MINT<M> operator - () const { return -v; }

    bool operator == (const MINT<M>& t) const { return v == t.v; }
    bool operator != (const MINT<M>& t) const { return v != t.v; }

    operator int32_t() const { return v; }
    operator int64_t() const { return v; }
};

template<int M>
void NTT(vector<MINT<M>>& a, bool inv_fft = false) {
    int n = a.size(); vector<MINT<M>> root(n / 2);
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n / 2;
        while (j >= bit) j -= bit, bit >>= 1;
        if (i < (j += bit)) swap(a[i], a[j]);
    }
    auto ang = MINT<M>::w.power((M - 1) / n); if (inv_fft) ang = ang.mul_inv();
    root[0] = 1; for (int i = 1; i < n / 2; i++) root[i] = root[i - 1] * ang;
    for (int i = 2; i <= n; i <<= 1) {
        int step = n / i;
        for (int j = 0; j < n; j += i) {
            for (int k = 0; k < i / 2; k++) {
                auto u = a[j + k], v = a[j + k + i / 2] * root[k * step];
                a[j + k] = u + v; a[j + k + i / 2] = u - v;
            }
        }
    }
    auto inv = MINT<M>(n).mul_inv();
    if (inv_fft) for (int i = 0; i < n; i++) a[i] = a[i] * inv;
}

template<typename T>
struct Poly {
    vector<T> a;
    Poly() : a() {}
    Poly(T a0) : a(1, a0) { normalize(); }
    Poly(const vector<T>& a) : a(a) { normalize(); }
    void normalize() { while (!a.empty() && a.back() == T(0)) a.pop_back(); }

    int size() const { return a.size(); }
    int deg() const { return size() - 1; }
    void push_back(const T& x) { a.push_back(x); }
    T get(int idx) const { return 0 <= idx && idx < size() ? a[idx] : T(0); }
    T& operator [] (int idx) { return a[idx]; }

    Poly reversed() const { auto b = a; reverse(b.begin(), b.end()); return b; }
    Poly trim(int sz) const { return vector<T>(a.begin(), a.begin() + min(sz, size())); }
    Poly inv(int n) const {
        Poly q(T(1) / a[0]);
        for (int i = 1; i < n; i <<= 1) {
            Poly p = Poly(2) - q * trim(i * 2);
            q = (p * q).trim(i * 2);
        }
        return q.trim(n);
    }

    Poly operator *= (const T& x) { for (auto& i : a) i *= x; normalize(); return *this; }
    Poly operator /= (const T& x) { return *this *= T(1) / x; }

    Poly operator += (const Poly& t) {
        a.resize(max(size(), t.size()));
        for (int i = 0; i < t.size(); i++) a[i] += t.a[i];
        normalize(); return *this;
    }
    Poly operator -= (const Poly& t) {
        a.resize(max(size(), t.size()));
        for (int i = 0; i < t.size(); i++) a[i] -= t.a[i];
        normalize(); return *this;
    }
    Poly operator *= (const Poly& t) {
        auto b = t.a;
        int n = 2; while (n < a.size() + b.size()) n <<= 1;
        a.resize(n); b.resize(n); NTT(a); NTT(b);
        for (int i = 0; i < n; i++) a[i] *= b[i];
        NTT(a, true); normalize(); return *this;
    }
    Poly operator /= (const Poly& t) {
        if (deg() < t.deg()) return *this = Poly();
        int sz = deg() - t.deg() + 1;
        Poly ra = reversed().trim(sz), rb = t.reversed().trim(sz).inv(sz);
        *this = (ra * rb).trim(sz);
        for (int i = sz - size(); i; i--) a.push_back(T(0));
        reverse(a.begin(), a.end()); normalize();
        return *this;
    }
    Poly operator %= (const Poly& t) {
        if (deg() < t.deg()) return *this;
        Poly tmp = *this; tmp /= t; tmp *= t;
        *this -= tmp; normalize();
        return *this;
    }

    Poly operator + (const Poly& t) const { return Poly(*this) += t; }
    Poly operator - (const Poly& t) const { return Poly(*this) -= t; }
    Poly operator * (const Poly& t) const { return Poly(*this) *= t; }
    Poly operator / (const Poly& t) const { return Poly(*this) /= t; }
    Poly operator % (const Poly& t) const { return Poly(*this) %= t; }
    Poly operator * (const T x) const { return Poly(*this) *= x; }
    Poly operator / (const T x) const { return Poly(*this) /= x; }

    T eval(T x) const {
        T res = 0;
        for (int i = deg(); i >= 0; i--) res = res * x + a[i];
        return res;
    }
    Poly derivative() const {
        vector<T> res;
        for (int i = 1; i < size(); i++) res.push_back(T(i) * a[i]);
        return res;
    }
    Poly integral() const {
        vector<T> res{ T(0) };
        for (int i = 0; i < size(); i++) res.push_back(a[i] / T(i + 1));
        return res;
    }
    Poly ln(int n) const {
        assert(size() > 0 && a[0] == T(1));
        return (derivative() * inv(n)).integral().trim(n);
    }
    Poly exp(int n) const {
        if (size() == 0) return Poly(1);
        assert(size() > 0 && a[0] == T(0));
        Poly res(1);
        for (int i = 1; i < n; i <<= 1) {
            auto t = Poly(1) + trim(i * 2) - res.ln(i * 2);
            res = (res * t).trim(i * 2);
        }
        return res.trim(n);
    }
    Poly pow(long long n) {
        // compute f(x)^n
        vector<T> b = a;
        b.resize(b.size() * n);
        int sz = 2;
        while (sz < b.size()) sz <<= 1;
        b.resize(sz);
        NTT(b);
        for (int i = 0; i < b.size(); i++) {
            b[i] = b[i].power(n);
        }
        NTT(b, true);
        return Poly(b);
    }
    Poly pow(long long n, int k) const {
        // compute f(x)^n mod x^k
        Poly acc(1), t = *this;
        t = t.trim(k);
        for (; n; n >>= 1) {
            if (n & 1) acc = (acc * t).trim(k);
            t = (t * t).trim(k);
        }
        return acc;
    }
};

using ModInt = MINT<1000000007>;
template<> ModInt ModInt::w = ModInt(3);

using T = ModInt;

// slow convolution
vector<ModInt> convolute_slow(vector<ModInt>& a, vector<ModInt>& b) {
    vector<ModInt> c(a.size() + b.size() - 1, ModInt(0));
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}
    

// O(N^3) lagrange interpolation
vector<ModInt> interpolate_slow(vector<ModInt> x_points, vector<ModInt> y_points) {
    int n = x_points.size();

    vector<ModInt> res(n, ModInt(0));
    for (int i = 0; i < n; ++i) {
        ModInt multiplier = 1;
        Poly<ModInt> num(1);
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            multiplier *= x_points[j] - x_points[i];
            vector<ModInt> one_term = {-x_points[j], 1};
            num = convolute_slow(num.a, one_term);
        }
        multiplier = y_points[i] / multiplier;
        for (int j = 0; j < n; ++j) {
            res[j] += num[j] * multiplier;
        }
    }
    return res;
}

template <typename T>
class Matrix {
public:
    vector<vector<T>> a;
    int n, m;
    Matrix() {}
    Matrix(int n, int m, vector<vector<T>> a) : n(n), m(m), a(a) {}
    Matrix<T> operator * (const Matrix<T>& b) {
        assert(m == b.n);
        vector<vector<T>> c(n, vector<T>(b.m, T(0)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < b.m; j++) {
                for (int k = 0; k < m; k++) {
                    c[i][j] += a[i][k] * b.a[k][j];
                }
            }
        }
        return Matrix<T>(n, b.m, c);
    }

    vector<T>& operator [] (int i) {
        return a[i];
    }
};

template <typename T>
class SquareMatrix : public Matrix<T> {
public:
    SquareMatrix() {}
    SquareMatrix(int n, vector<vector<T>> a) : Matrix<T>(n, n, a) {}

    static SquareMatrix<T> identity(int n) {
        vector<vector<T>> a(n, vector<T>(n, T(0)));
        for (int i = 0; i < n; i++) {
            a[i][i] = T(1);
        }
        return SquareMatrix<T>(n, a);
    }

    SquareMatrix<T> operator * (const SquareMatrix<T>& b) {
        return SquareMatrix<T>(this->n, Matrix<T>::operator*(b).a);
    }

    SquareMatrix<T> pow(long long k) {
        SquareMatrix<T> res = SquareMatrix<T>::identity(this->n);
        SquareMatrix<T> a = *this;
        for (; k; k >>= 1) {
            if (k & 1) {
                res = res * a;
            }
            a = a * a;
        }
        return res;
    }

    T determinant() {
        int n = this->n;
        vector<vector<T>> b = this->a;
        T det = T(1);
        for (int i = 0; i < n; i++) {
            int idx = -1;
            for (int j = i; j < n; j++) {
                if (b[j][i] != T(0)) {
                    idx = j;
                    break;
                }
            }
            if (idx == -1) {
                return T(0);
            }
            if (i != idx) {
                det = -det;
                swap(b[i], b[idx]);
            }
            if (b[i][i] == T(0)) {
                return T(0);
            }
            det *= b[i][i];
            T inv = b[i][i].mul_inv();
            for (int j = i + 1; j < n; j++) {
                b[i][j] *= inv;
            }
            for (int j = i + 1; j < n; j++) {
                for (int k = i + 1; k < n; k++) {
                    b[j][k] -= b[j][i] * b[i][k];
                }
            }
        }
        return det;
    }

    int rank() {
        int n = this->n;
        vector<vector<T>> b = this->a;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int idx = -1;
            for (int j = i; j < n; j++) {
                if (b[j][i] != T(0)) {
                    idx = j;
                    break;
                }
            }
            if (idx == -1) {
                continue;
            }
            res++;
            if (i != idx) {
                swap(b[i], b[idx]);
            }
            T inv = b[i][i].mul_inv();
            for (int j = i + 1; j < n; j++) {
                b[i][j] *= inv;
            }
            for (int j = i + 1; j < n; j++) {
                for (int k = i + 1; k < n; k++) {
                    b[j][k] -= b[j][i] * b[i][k];
                }
            }
        }
        return res;
    }
};



int N, M, G, B;

int a, b, c;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> G >> B;

    if (N == 1) {
        cout << 1 << '\n';
        return 0;
    }

    vector<vector<SquareMatrix<ModInt>>> dp(N, vector<SquareMatrix<ModInt>>(N, SquareMatrix<ModInt>(N - 1, vector<vector<ModInt>>(N - 1, vector<ModInt>(N - 1, ModInt(0))))));

    vector<SquareMatrix<ModInt>> storage(3, SquareMatrix<ModInt>(N - 1, vector<vector<ModInt>>(N - 1, vector<ModInt>(N - 1, ModInt(0)))));

    while (M--) {
        cin >> a >> b >> c;
        a--, b--; c--;
        if (a != N - 1) {
            storage[c][a][a] += 1;
        }
        if (b != N - 1) {
            storage[c][b][b] += 1;
        }
        if (a != N - 1 && b != N - 1) {
            storage[c][a][b] -= 1;
            storage[c][b][a] -= 1;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int inner_i = 0; inner_i < N - 1; inner_i++) {
                for (int inner_j = 0; inner_j < N - 1; inner_j++) {
                    dp[i][j][inner_i][inner_j] = storage[0][inner_i][inner_j];
                    dp[i][j][inner_i][inner_j] += storage[1][inner_i][inner_j] * ModInt(i);
                    dp[i][j][inner_i][inner_j] += storage[2][inner_i][inner_j] * ModInt(j);
                }
            }
        }
    }

    vector<vector<ModInt>> determinants(N, vector<ModInt>(N, ModInt(0)));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            determinants[i][j] = dp[i][j].determinant();
        }
    }
    
    vector<ModInt> iota(N, ModInt(0));
    for (int i = 0; i < N; i++) {
        iota[i] = i;
    }

    for (int i = 0; i < N; i++) {
        vector<ModInt> interpolate_vector;
        for (int j = 0; j < N; j++) {
            interpolate_vector.push_back(determinants[i][j]);
        }
        interpolate_vector = interpolate_slow(iota, interpolate_vector);
        for (int j = 0; j < N; j++) {
            determinants[i][j] = interpolate_vector[j];
        }
    }

    for (int j = 0; j < N; j++) {
        vector<ModInt> interpolate_vector;
        for (int i = 0; i < N; i++) {
            interpolate_vector.push_back(determinants[i][j]);
        }
        interpolate_vector = interpolate_slow(iota, interpolate_vector);
        for (int i = 0; i < N; i++) {
            determinants[i][j] = interpolate_vector[i];
        }
    }

    ModInt ans = 0;

    for (int i = 0; i <= G; i++) {
        for (int j = 0; j <= B; j++) {
            ans += determinants[i][j];
        }
    }

    cout << ans << '\n';

    return 0;
}