小O有一个n个点，m条边的边带权无向图。小O希望从这m条边中，选出一些边，使得这些边能构成这n个点的生成树。但他还有个幸运数字k。因此他希望最终选出来的这些边的权值和是k的倍数。他想知道最终有多少种可能的方案选出合法的生成树。答案可能很大，幸好小O还有一个幸运质数p。你只需要输出答案对p取模即可。
输入描述:
第一行四个个整数n, m, k, p。
接下来m行，每行三个整数u,v,c，代表这条边连接u,v两点，边权为c。点标号为1到n。
数据保证1 ≤ n,k ≤ 100, 0 ≤ m ≤ 10000, 1 ≤ u,v ≤ n, 0 ≤ c < k。p是质数且p mod k = 1，且p ≤ 10⁹。

输出描述:
一行一个整数代表方案数对p取模的值。
示例1
输入
5 10 4 60661
4 2 2
2 1 1
4 3 3
1 5 0
2 5 0
2 1 1
2 3 3
3 4 3
4 1 1
3 5 0
输出
14

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110;
struct node
{
	ll x,y,w;
}e[N*N];
ll n,m,k,P,g,x[N],y[N];
vector<ll> p;
ll power(ll x,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
void Prime()
{
	ll x=P-1;
	for(ll i=2;i*i<=x;i++)
		if(x%i==0)
		{
			p.push_back(i);
			while(x%i==0)x/=i;
		}
	if(x>1)p.push_back(x);
}
bool check(ll x)
{
	for(ll i=0;i<p.size();i++)
		if(power(x,(P-1)/p[i])==1)return 0;
	return 1;
}
namespace Matrix
{
	ll a[N][N];
	ll det(ll v)
	{
		memset(a,0,sizeof(a));
		ll ans=1;
		for(ll i=1;i<=m;i++)
		{
			ll x=e[i].x,y=e[i].y,w=power(v,e[i].w); 
			(a[x][y]+=P-w)%=P;(a[y][x]+=P-w)%=P;
			(a[x][x]+=w)%=P;(a[y][y]+=w)%=P;
		}
		ll f=0;
		for(ll i=1;i<n;i++)
		{
			for(ll j=i;j<n;j++)
				if(a[j][i])
				{
					if(i==j)break;
					swap(a[i],a[j]);
					f^=1;break;
				}
			ans=ans*a[i][i]%P;
			ll inv=power(a[i][i],P-2);
			for(ll j=i;j<n;j++)a[i][j]=a[i][j]*inv%P;
			for(ll j=i+1;j<n;j++)
			{
				ll rate=P-a[j][i];
				for(ll k=i;k<n;k++)
					(a[j][k]+=rate*a[i][k])%=P;
			}
		}
		return f?(P-ans):ans;
	}
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&k,&P);
	Prime();g=1;
	while(!check(g)) g++;
	for(ll i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].w);
	for(ll i=1;i<=k;i++)
	{
		x[i]=power(g,(P-1)/k*(i-1));
		y[i]=Matrix::det(x[i]);
	}
	ll ans=0;
	for(ll i=1;i<=k;i++)
	{
		ll tmp=1;
		for(ll j=1;j<=k;j++)
			if(i!=j)tmp=tmp*(P-x[j])%P*power(x[i]-x[j],P-2)%P;
		(ans+=tmp*y[i]%P)%=P;
	}
	printf("%lld\n",(ans+P)%P);
	return 0;
}