题号：NC18393
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小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 ≤ 109。
输出描述:
一行一个整数代表方案数对p取模的值。