我们的神仙教练在考试里放了这道题，当时我非常惊讶啊
背包是(O(n^3))的吧明明是带根号的好吧，那既然要优化的话
NTT！什么时候我们教练会在考试里放多项式了
模数(1e9+7)？
任意模数不存在的，我们开int128找一个大一点的(NTT)模数就可以了
还是说一下(NTT)的做法吧，发现我们要求长度大于(Y)的路径可能不太好求，于是我们正难则反一下，我们求出有多少种拼法可以使得路径长度小于(Y)就可以了
每一棵树里只能出一条路径，于是我们可以把一棵树的路径信息搞成一个多项式，系数代表这种长度的路径出现了多少次
我们把每棵树的多项式卷起来就是最后的答案了
并不保证随时能通过而且我们不怎么能看懂的代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define _LL __int128
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#pragma GCC optimize(3)
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("Ofast,no-stack-protector")
char BB[1<<18],*S=BB,*T=BB;
const int maxn=1505;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,w;}e[maxn<<1];
const LL mod=4222124650659841;
const LL P=1e9+7;
_LL G[2],t,og;
_LL mi[2][16];
int head[maxn],sum[maxn];
int n,m,X,Y,tot,num;
int rev[10000],len,fa[maxn],vis[maxn],pre[maxn];
int tax[1501][2501];LL tp[maxn];
_LL A[9000],B[9000];
LL tmp=1,k=0;
inline void add(int x,int y,int w) {
e[++num].v=y;e[num].nxt=head[x];
head[x]=num;e[num].w=w;
}
inline _LL ksm(_LL a,LL b) {
_LL S=1;
while(b) {if(b&1ll) S=S*a%mod;b>>=1ll;a=a*a%mod;}
return S;
}
void exgcd(LL a,LL b,LL &x,LL &y) {
if(!b) {x=1,y=0;return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
inline LL getInv(LL a) {
LL x,y;exgcd(a,P,x,y);
return (x%P+P)%P;
}
void write(LL x){
if(x==0){putchar(48);return;}
int len=0,dg[25];
while(x>0){dg[++len]=x%10ll;x/=10ll;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void NTT(_LL *f,int o) {
for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
for(re int i=2,k=0;i<=len;i<<=1,k++) {
int ln=i>>1;
LL og1;
if(!mi[o][k]) {mi[o][k]=og1=ksm(G[o],(mod-1)/i);}
else og1=mi[o][k];
for(re int l=0;l<len;l+=i) {
og=1;
for(re int x=l;x<ln+l;++x) {
t=(f[ln+x]*og)%mod;
f[ln+x]=(f[x]-t+mod)%mod;
f[x]=(f[x]+t)%mod;
og=(og*og1)%mod;
}
}
}
if(!o) return;
_LL inv=ksm(len,mod-2);
for(re int i=0;i<len;i++) f[i]=(f[i]*inv)%mod;
}
void dfs(int x,int Fa) {
++k;
fa[x]=Fa;vis[x]=1;
for(re int i=head[x];i;i=e[i].nxt) {
if(vis[e[i].v]) continue;
dfs(e[i].v,Fa);
}
}
void Dfs(int x,int fa,int p) {
for(re int i=head[x];i;i=e[i].nxt) {
if(e[i].v==fa) continue;
pre[e[i].v]=pre[x]+e[i].w;
if(pre[e[i].v]<Y) tax[p][pre[e[i].v]]++;
else tp[p]+=pre[e[i].v];
Dfs(e[i].v,x,p);
}
}
inline void mul() {
NTT(A,0),NTT(B,0);
for(re int i=0;i<len;i++) A[i]=(A[i]*B[i])%mod;
NTT(A,1);
for(re int i=0;i<Y;i++) A[i]%=P;
//中间取模的简易版任意模数NTT
for(re int i=Y;i<len;i++) A[i]=0;
}
int main() {
G[0]=19ll,G[1]=ksm(19ll,mod-2);
n=read(),m=read(),X=read(),Y=read();
for(re int x,y,z,i=1;i<=m;i++)
x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
LL cnt=0,H=0,T=0;
for(re int i=1;i<=n;i++)
if(!vis[i]) {
k=0;++tot,dfs(i,tot);
k=k*(k-1ll)/2ll;sum[tot]=k;
tmp=(tmp*k)%P;
}
Y-=tot*X;
for(re int i=1;i<=n;i++) pre[i]=0,Dfs(i,0,fa[i]);
A[0]=1;len=1;while(len<Y+Y) len<<=1;
for(re int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?len>>1:0);
for(re int i=1;i<=tot;i++) {
for(re int j=0;j<len;j++) B[j]=0;
LL inv=tmp*getInv(sum[i])%P;
for(re int j=0;j<Y;j++) {
B[j]=(tax[i][j]/2);
H+=(inv*(LL)j%P*(LL)(tax[i][j]/2ll)%P);
H%=P;
}
H+=inv*(tp[i]/2ll)%P;H%=P;
mul();
}
//H是所有环的长度和，tmp是所有环的方案数
//cnt是不满足条件的环的方案数，T是不满足条件的环的长度和
for(re int i=1;i<Y;i++)
cnt=(cnt+A[i])%P,T=(T+A[i]*(LL)i%P)%P;
H=(H-T+P)%P;
tmp=(tmp-cnt+P)%P;
H+=tmp*(LL)tot%P*(LL)X%P;H%=P;
if(tot==1) {write(H);return 0;}
if(tot==2) write(H*2ll%P);
else {
LL pw=2,now=4;tot-=2;
for(re int i=1;i<=tot;i++)
pw=(pw*now)%P,now=(now+2ll)%P;
write(H*pw%P);
}
return 0;
}