1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
| #include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define LL long long
#define DB double
#define STC static
#define IL inline
using namespace std;
namespace Fast
{
const int L = (1 << 20) + 5;
char buf[L], out[L], *iS, *iT;
int l = 0;
#define gh() (iT == iS ? iT = (iS = buf) + fread(buf, 1, L, stdin), (iT == iS ? EOF : *iS++) : *iS++)
template<class T>
IL void read(T &x)
{
x = 0;
char ch = gh(), t = 0;
while (ch < '0' || ch > '9')
t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9')
x = x * 10 + (ch ^ 48), ch = gh();
if (t)
x = -x;
}
IL void flus()
{
fwrite(out, 1, l, stdout);
l = 0;
}
IL void putc(char x)
{
out[l++] = x;
if (l == L - 5)
flus();
}
template<class T>
IL void write(T x)
{
if (x < 0)
putc('-'), x = -x;
if (x > 9)
write(x / 10);
out[l++] = x % 10 + 48;
if (l == L - 5)
flus();
}
}
using Fast::flus;
using Fast::putc;
using Fast::read;
using Fast::write;
const int N = 1500 + 5, P = 1e9 + 7, V = 2500 + 5;
int n, m, X, Y;
int fa[N];
struct Egde
{
int ne, ver, w;
} e[N << 1];
int h[N], idx = 0;
int cnt = 0, bel[N];
int g[N][V][2];
int d[V][2], last[V][2];
IL void add(int x, int y, int z)
{
e[idx] = {h[x], y, z}, h[x] = idx++;
}
IL int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
IL void dfscol(int x, int ff, int col)
{
bel[x] = col;
for (int i = h[x]; i != -1; i = e[i].ne)
if (e[i].ver != ff)
dfscol(e[i].ver, x, col);
}
IL void dfslen(int x, int ff, int l)
{
if (ff != -1)
{
g[bel[x]][min(Y, l)][1] += l;
g[bel[x]][min(Y, l)][1] %= P;
++g[bel[x]][min(Y, l)][0];
}
for (int i = h[x]; i != -1; i = e[i].ne)
if (e[i].ver != ff)
dfslen(e[i].ver, x, l + e[i].w);
}
IL int fac(int x)
{
int res = 1;
for (int i = 2; i <= x; ++i)
res = (LL)res * i % P;
return res;
}
int main()
{
read(n), read(m), read(X), read(Y);
for (int i = 1; i <= n; ++i)
fa[i] = i, h[i] = -1;
for (int i = 1, u, v, w; i <= m; ++i)
{
read(u), read(v), read(w);
add(u, v, w), add(v, u, w);
fa[find(u)] = find(v);
}
for (int i = 1; i <= n; ++i)
if (find(i) == i)
++cnt, dfscol(i, -1, cnt);
for (int i = 1; i <= n; ++i)
dfslen(i, -1, 0);
int st = min(X * cnt, Y);
d[st][0] = 1, d[st][1] = X * cnt;
for (int i = 1; i <= cnt; ++i)
{
for (int j = st; j <= Y; ++j)
last[j][0] = d[j][0], last[j][1] = d[j][1], d[j][0] = d[j][1] = 0;
for (int j = 0; j <= Y; ++j)
if (g[i][j][0])
for (int k = st; k <= Y; ++k)
if (last[k][0])
{
d[min(j + k, Y)][0] = (d[min(j + k, Y)][0] + (LL)last[k][0] * g[i][j][0]) % P;
d[min(j + k, Y)][1] = (d[min(j + k, Y)][1] + (LL)last[k][0] * g[i][j][1] + (LL)last[k][1] * g[i][j][0]) % P;
}
}
printf("%lld\n", (LL)d[Y][1] * fac(cnt - 1) % P * ((P + 1) / 2) % P);
return flus(), 0;
}
|