#include //#include //#include #define int long long #define ld long double #define get(T,args...) T args; read(args); #define init(a,T,n,s) vector a((n)+1,s); cin>>a; #define putn(args...) { put(args); cout<<"\n"; } #define pute(args...) { put(args); cout<(b); i--) #define logarr(arr,f,l) { auto start=arr.begin(), end=arr.begin(); advance(start,(f)); advance(end,(l)); for(auto it=start; it!=end; it++) cout<<*it<<" "; cout<<"\n"; } #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sort_by(span,p) sort(span, [&](const auto &l, const auto &r) { return p; }) #define f(u, args...) [&](auto &&u) { return args; } #define g(u, v, args...) [&](auto &&u, auto &&v) { return args; } #define uniq(x) x.erase(unique(all(x)),x.end()); #define sz(x) (int)(x).size() #define mid(l,r) std::midpoint((l),(r)) #define zov(v,z,c) ((c) ? (v) : (z)) #define pii pair #define pb emplace_back #define pf push_front #define fr first #define sc second #define sumv(v,b,e) accumulate((v).begin()+b,(v).begin()+e,0LL) #define minv(v,b,e) min_element((v).begin()+b,(v).begin()+e) #define maxv(v,b,e) max_element((v).begin()+b,(v).begin()+e) #define precise(n) cout< #define set(args...) std::set > #define pqueue(args...) std::priority_queue,Comp > //#define oset(args...) tree, rb_tree_tag, tree_order_statistics_node_update> const int N = 100001, M = 998244353, mod = 1000000007, MX = INT64_MAX, MN = INT64_MIN, oo = 1e18; #ifdef DEBUG #include "./Debug/debug.hpp" #else #define debug(args...) 0; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif //using namespace __gnu_pbds; using namespace std; vec(string) tokenizer(string str,char ch) {std::istringstream var((str)); vec(string) v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;} template struct Comp { bool operator()(const T& l, const T& r) const { return l < r; } }; template inline istream& operator >> (istream& in, pair& a) { in>>a.first>>a.second; return in; } template inline ostream& operator << (ostream& out, pair a) { out< istream& operator >> (istream& in, vector& v) { rep(i,1,sz(v)) cin>>v[i]; return in; } template inline bool amax(T &a,T1 b){ if(b>a) { a=b; return true; } return false; } template inline bool amin(T &a,T1 b){ if(b>args), ...); } void put(auto&&... args) { ((cout< par, sizes; public: DSU(int n) : par(n+1), sizes(n+1,1) { for(int i=1; i<=n; i++) par[i] = i; } int find_set(int x) { return par[x] = (par[x] == x) ? x : find_set(par[x]); } bool merge(int x, int y) { x = find_set(x); y = find_set(y); if(x == y) return false; if(sizes[y] > sizes[x]) swap(x,y); sizes[x] += sizes[y]; par[y] = x; return true; } int get_size(int x) { return sizes[find_set(x)]; } }; long long expm(long long a, long long b, long long m=mod) { long long res=1; while(b) { if(b & 1) { res=((res % m) * (a % m)) % m; } b/=2; a=((a % m) * (a % m)) % m; } return res; } void solve(int T) { get(int,n) vector> edges(n-1); for(auto&[a,b,w]:edges) cin>>a>>b>>w; int ans = 0; rep(i,0,32) { DSU dsu(n); for(auto& [a,b,w]:edges) { if((w>>i)&1) { dsu.merge(a,b); } } rep(j,1,n+1) { if(dsu.find_set(j) == j) { int sz = dsu.get_size(j); int val = ((((sz*(sz-1))%mod) * expm(2,mod-2,mod))%mod); ans = (ans + (val*(1LL<