一个看起来挺经典的题。

$$n\le 40 , m\le 10^5$$

---

我们可以先考虑只有两种颜色的情况。比如只有 Red and Blue。

我们设红边权值为 $1$ ，蓝边权值为 $x$ ，那么我们可以写出一个生成函数 $F(x)$ ，并且可以设 $x^i$ 的系数是选择正好 $i$ 条蓝色边的方案数量，也就是选择正好 $i$ 条边的答案。

只要求出这个多项式的系数就好了。于是我们可以考虑对 $F(x)$ 在 $0\dots n$ 插值，插出 $n+1$ 个点值拉格朗日插值即可。插值的过程其实就是一个求生成树个数的过程，直接上矩阵树定理，复杂度 $O(n^4)$。

加入绿色边后能不能一样地做呢？我们可以设绿色边的边权是 $x^n$ ，那么总生成函数长度就是 $O(n^2)$ ，同样插值即可，复杂度 $O(n^5)$。

其实今天貌似是第一次做拉格朗日插值。。我们设

$$\ell_j(x) = \prod_{i\neq j} \frac{x-x_j}{x_i-x_j}\\f(x) = \sum_{i=1}^n y_i \ell_i(x)$$

然后我们可以先求出 $\prod x-x_j$ 然后做多项式除法求 $\ell_i$ ，这样做复杂度就是 $O(n^2)$。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 46
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 1000000007
int n , m , x , y;
int G[3][MAXN][MAXN] , deg[3][MAXN];
int g[MAXN * MAXN] , f[MAXN * MAXN] , h[MAXN * MAXN];
// g : \prod x - i , f : sum of h , h : \prod x-j / ( x - i )

inline int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

int F[MAXN][MAXN];

inline int lsj( ) {
    int t = n - 1;
    int ans = 1;
    rep( i , 1 , t ) {
        int cur = -1;
        rep( j , i , t ) if( F[j][i] ) {
            cur = j; break;
        }
        if( cur == -1 ) continue;
        if( cur != i )
            swap( F[cur] , F[i] ) , ans = -ans;
        rep( j , i + 1 , t ) {
            int r = F[j][i] * 1ll * Pow( F[i][i] , P - 2 ) % P;
            rep( k , 1 , t ) F[j][k] = ( F[j][k] + P - 1ll * r * F[i][k] % P ) % P;
        }
    }
    rep( i , 1 , t ) ans = 1ll * ans * F[i][i] % P;
    return ans;
}

inline int work( int t ) {
    mem( F );
    int qb = t , ql = Pow( t , n );
    for( int i = 1 ; i <= n ; ++ i )
        F[i][i] = ( F[i][i] + deg[0][i] ) % P ,
        F[i][i] = ( F[i][i] + deg[1][i] * 1ll * qb % P ) % P ,
        F[i][i] = ( F[i][i] + deg[2][i] * 1ll * ql % P ) % P ;
    for( int i = 1 ; i <= n ; ++ i )
        for( int j = 1 ; j <= n ; ++ j )
            F[i][j] = ( F[i][j] + P - G[0][i][j] ) % P ,
            F[i][j] = ( F[i][j] + 1ll * ( P - G[1][i][j] ) * qb ) % P ,
            F[i][j] = ( F[i][j] + 1ll * ( P - G[2][i][j] ) * ql ) % P ;
    return lsj( );
}

void solve() {
    cin >> n >> m >> x >> y;
    int u , v , w;
    rep( i , 1 , m ) {
        scanf("%d%d%d",&u,&v,&w) , -- w;
        if( u == v ) continue;
        ++ G[w][u][v] , ++ G[w][v][u];
        ++ deg[w][u] , ++ deg[w][v];
    }
    g[0] = 1;
    int tot = n * ( n - 1 );
    for( int i = 0 ; i <= tot ; ++ i )
        for( int j = i ; j >= 0 ; -- j )
            ( g[j + 1] += g[j] ) %= P , g[j] = ( P - 1ll * g[j] * i % P ) % P;
    for( int i = 0 ; i <= tot ; ++ i ) {
        int pr = work( i );
        rep( j , 0 , tot ) if( i != j ) pr = pr * 1ll * ( i < j ? P - Pow( j - i , P - 2 ) : Pow( i - j , P - 2 ) ) % P;
        rep( j , 0 , tot + 1 ) h[j] = g[j];
        per( j , tot + 1 , 1 ) h[j - 1] = ( h[j - 1] + h[j] * 1ll * i % P ) % P;
        rep( j , 0 , tot ) f[j] = ( f[j] + h[j + 1] * 1ll * pr % P ) % P;
    }
    int res = 0;
    rep( i , 0 , tot )
        if( i % n <= x && i / n <= y ) res = ( res + f[i] ) % P;
    cout << res << endl;
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}