func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 3e5 + 5, P = 1e9 + 7;   struct Edge {     int v, nxt, col;     long long w;   } e[N << 1];   int head[N], size = 1, ext;   long long ans = 1;   long long qpow(long long a, long long b) {     long long res = 1;     while (b) {       if (b & 1) res = res * a % P;       a = a * a % P;       b >>= 1;     }     return res;   }   void link(int u, int v, long long w, int col) {     e[++size].v = v;     e[size].nxt = head[u];     e[size].w = w;     e[size].col = col;     head[u] = size;   }   int read() {     int x = 0, f = 1;     char c = getchar();     while (c >  9  || c <  0 ) {       if (c ==  - ) f = -1;       c = getchar();     }     while (c >=  0  && c <=  9 ) {       x = x * 10 + c -  0 ;       c = getchar();     }     return x * f;   }   namespace sdh {   struct Node {     int v, w, col;     Node() {}     Node(int _v, int _w, int _col) {       v = _v;       w = _w;       col = _col;     }   } stk[N];   int top;   vector<Node> e[N];   void dfs(int u, int fa) {     top = 0;     for (Node v : e[u]) {       if (v.v == fa) continue;       stk[++top] = v;     }     int lst = u;     for (int i = 1; i <= top - 2; ++i) {       Node c = stk[i];       link(lst, c.v, c.w, c.col);       link(c.v, lst, c.w, c.col);       ++ext;       link(lst, ext, 1, -1);       link(ext, lst, 1, -1);       lst = ext;     }     if (top > 0)       link(lst, stk[top].v, stk[top].w, stk[top].col),           link(stk[top].v, lst, stk[top].w, stk[top].col);     if (top > 1)       link(lst, stk[top - 1].v, stk[top - 1].w, stk[top - 1].col),           link(stk[top - 1].v, lst, stk[top - 1].w, stk[top - 1].col);     for (Node v : e[u]) {       if (v.v == fa) continue;       dfs(v.v, u);     }   }   }  // namespace sdh   int max(int x, int y) { return x > y ? x : y; }   int n, RT, MN, sze[N], SZE;   bool vis[N << 1];   void findrt(int u, int fa) {     sze[u] = 1;     for (int i = head[u]; i; i = e[i].nxt) {       int v = e[i].v;       if (v == fa || vis[i]) continue;       findrt(v, u);       sze[u] += sze[v];       if (MN > max(sze[v], SZE - sze[v])) {         MN = max(sze[v], SZE - sze[v]);         RT = i;       }     }   }   struct Q {     int x, y, opt;     long long val;   } q[N], type[N];   bool cmp(Q p, Q q) {     if (p.x != q.x)       return p.x < q.x;     else       return p.opt < q.opt;   }   int tot;   void dfsA(int u, int fa, int B, int W, long long val) {     if (u <= n) {       q[++tot].x = 2 * W - B;       q[tot].y = 2 * B - W;       q[tot].val = val;       q[tot].opt = 1;     }     for (int i = head[u]; i; i = e[i].nxt) {       int v = e[i].v;       if (v == fa || vis[i]) continue;       if (e[i].col == 0) dfsA(v, u, B + 1, W, val * e[i].w % P);       if (e[i].col == 1) dfsA(v, u, B, W + 1, val * e[i].w % P);       if (e[i].col == -1) dfsA(v, u, B, W, val * e[i].w % P);     }   }   void dfsB(int u, int fa, int B, int W, long long val) {     if (u <= n) {       q[++tot].x = B - 2 * W;       q[tot].y = W - 2 * B;       q[tot].val = val;       q[tot].opt = 0;     }     for (int i = head[u]; i; i = e[i].nxt) {       int v = e[i].v;       if (v == fa || vis[i]) continue;       if (e[i].col == 0) dfsB(v, u, B + 1, W, val * e[i].w % P);       if (e[i].col == 1) dfsB(v, u, B, W + 1, val * e[i].w % P);       if (e[i].col == -1) dfsB(v, u, B, W, val * e[i].w % P);     }   }   void Cdq(int l, int r) {     if (l >= r) return;     int mid = (l + r) >> 1;     Cdq(l, mid);     Cdq(mid + 1, r);     long long sum = 0, prod = 1;     int i = l, j = mid + 1;     while (j <= r) {       while (i <= mid && q[i].y <= q[j].y) {         if (q[i].opt == 0) {           ++sum;           (prod *= q[i].val) %= P;         }         ++i;       }       if (q[j].opt == 1) {         ans = ans * qpow(q[j].val, sum) % P * prod % P;       }       ++j;     }     i = l;     j = mid + 1;     int tot = 0;     while (i <= mid && j <= r) {       if (q[i].y < q[j].y)         type[++tot] = q[i++];       else         type[++tot] = q[j++];     }     while (i <= mid) type[++tot] = q[i++];     while (j <= r) type[++tot] = q[j++];     for (int i = l; i <= r; ++i) q[i] = type[i - l + 1];   }   void calc(int u) {     int U = e[u].v, V = e[u ^ 1].v;     tot = 0;     if (e[u].col == 0) dfsA(U, 0, 1, 0, e[u].w);     if (e[u].col == 1) dfsA(U, 0, 0, 1, e[u].w);     if (e[u].col == -1) dfsA(U, 0, 0, 0, e[u].w);     dfsB(V, 0, 0, 0, 1);     sort(q + 1, q + tot + 1, cmp);     Cdq(1, tot);   }   void Divide(int u) {     if (!u) return;     vis[u] = vis[u ^ 1] = 1;     calc(u);     int U = e[u].v, V = e[u ^ 1].v, totsze = SZE, szeU = sze[U], szeV = sze[V];     RT = 0;     MN = P;     SZE = szeU > szeV ? totsze - szeV : szeU;     findrt(U, 0);     Divide(RT);     RT = 0;     MN = P;     SZE = szeV > szeU ? totsze - szeU : szeV;     findrt(V, 0);     Divide(RT);   }   int main() {     n = read();     for (int i = 1; i < n; ++i) {       int u = read(), v = read(), w = read(), col = read();       sdh::e[u].push_back(sdh::Node(v, w, col));       sdh::e[v].push_back(sdh::Node(u, w, col));     }     ext = n;     sdh::dfs(1, 0);     RT = 0;     SZE = ext;     MN = P;     findrt(1, 0);     Divide(RT);     printf( %lld , ans);     return 0;   }   