text: h> using namespace std; inline int read() { static int r, sign; static char c; r = 0, sign = 1; do c = getchar(); while (c != '-' && (c < '0' || c > '9')); if (c == '-') sign = -1, c = getchar(); while (c >= '0' && c <= '9') r = r * 10 + (int)(c - '0'), c = getchar(); return sign * r; } template <typename T> inline void print(T *a, int n) { for (int i = 1; i < n; ++i) cout << a[i] << " "; cout << a[n] << endl; } const int mod = (int)1e9 + 7; struct hashInt { int x; hashInt() {} hashInt(int _x) : x(_x) {} inline hashInt operator+(const hashInt &y) const { int z = x + y.x; if (z >= mod) z -= mod; if (z < 0) z += mod; return hashInt(z); } inline hashInt operator-(const hashInt &y) const { int z = x - y.x; if (z >= mod) z -= mod; if (z < 0) z += mod; return hashInt(z); } inline hashInt operator*(const hashInt &y) const { return hashInt((long long)x * y.x % mod); } }; struct edge { int next, node; hashInt w; } e[100100 << 1 | 1]; int head[100100 + 1], tot = 0; inline void addedge(int a, int b, int w) { e[++tot].next = head[a]; head[a] = tot, e[tot].node = b, e[tot].w = w; } struct DP { hashInt sum, sqr; DP() {} DP(int _s, int _q) : sum(_s), sqr(_q) {} DP(hashInt _s, hashInt _q) : sum(_s), sqr(_q) {} } up[100100 + 1], down[100100 + 1], downex[100100 + 1]; int n, size[100100 + 1]; inline hashInt delta(const DP &x, int n, hashInt b) { return x.sqr + b * b * n + b * 2 * x.sum; } void preUp(int x, int f) { size[x] = 1, up[x].sum = up[x].sqr = 0; for (int i = head[x]; i; i = e[i].next) { int node = e[i].node; if (node == f) continue; preUp(node, x); size[x] += size[node]; up[x].sum = up[x].sum + up[node].sum + e[i].w * size[node]; up[x].sqr = up[x].sqr + delta(up[node], size[node], e[i].w); } } void preDown(int x, int f) { for (int i = head[x]; i; i = e[i].next) { int node = e[i].node; if (node == f) continue; DP cur; cur.sum = down[x].sum + up[x].sum - up[node].sum - e[i].w * size[node]; cur.sqr = down[x].sqr + up[x].sqr - delta(up[node], size[node], e[i].