#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; using mint = modint1000000007; const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; //const bool debug = false; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } struct Edge { int to, cost; Edge(int _to, int _cost) :to(_to), cost(_cost) {} }; vectorg[200005]; long long a[200005]; long long b[200005]; vectorw; bool ng; long long val; void dfs(int v, int p = -1) { w.push_back(v); for (Edge e : g[v]) { //if (p == e.to) continue; if (0 == a[e.to]) { a[e.to] = -a[v]; b[e.to] = e.cost - b[v]; dfs(e.to, v); } else if (a[v] != a[e.to]) { if (e.cost != b[v] + b[e.to]) { ng = true; //cout << "d" << endl; break; } } else { if (-1 == val) { if (0 != (e.cost - b[v] - b[e.to]) % 2) { ng = true; //cout << "b" << endl; break; } int nval = ((e.cost - b[v] - b[e.to]) / 2) *a[v]; if (nval <= 0) { ng = true; //cout << v << " " << e.to << endl; //cout << nval << endl; //cout << "c" << endl; break; } val = nval; } else { int s = a[v] * val + b[v]; int t = a[e.to] * val + b[e.to]; if (e.cost != s + t) { ng = true; //cout << "a" << endl; break; } } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vectorx(m), y(m), z(m); dsu uf(n); rep(i, m) { int x, y, z; cin >> x >> y >> z; x--; y--; g[x].emplace_back(y, z); g[y].emplace_back(x, z); } mint c1 = 1, c2 = 1; rep(i, n) { if (0 != a[i]) continue; a[i] = 1; b[i] = 0; w.clear(); val = -1; dfs(i); if (ng) { //rep(j, n) { // cout << a[j] << " " << b[j] << endl; //} cout << 0 << endl; return 0; } if (-1 == val) { { long long l = 1; long long r = k; rep(j, w.size()) { if (1 == a[w[j]]) { //0 < x + b[] <= k // -b[] < x <= k-x chmax(l, 1 - b[w[j]]); chmin(r, k - b[w[j]]); } else { //0 < -x+b[] <= k // b[]-k <= x < b[] chmax(l, b[w[j]] - k); chmin(r, b[w[j]] - 1); } } c1 *= max(0LL, r - l + 1); } { long long l = 1; long long r = k - 1; rep(j, w.size()) { if (1 == a[w[j]]) { //0 < x + b[] <= k - 1 // -b[] < x <= k - 1 -x chmax(l, 1 - b[w[j]]); chmin(r, (k - 1) - b[w[j]]); } else { //0 < -x+b[] <= k - 1 // b[]-(k - 1) <= x < b[] chmax(l, b[w[j]] - (k - 1)); chmin(r, b[w[j]] - 1); } } c2 *= max(0LL, r - l + 1); } } else { rep(j, w.size()) { long long x = a[w[j]] * val + b[w[j]]; if (x <= 0) { c1 = 0; c2 = 0; } else if (x == k) { c2 = 0; } else if (x > k) { c1 = 0; c2 = 0; } } } } cout << (c1 - c2).val() << endl; return 0; }