#abc201e. [abc201_e]Xor Distances

[abc201_e]Xor Distances

問題文

NN 頂点の重み付き木があります。ii 本目の辺は頂点 uiu_i と頂点 viv_i を双方向に結んでいて、その重みは wiw_i です。

頂点の組 (x,y)(x,y) について、textdist(x,y)\\text{dist}(x,y) を以下のように定めます。

  • xx から yy への最短パスに含まれる辺全ての重みの XOR

1leqiltjleqN1 \\leq i \\lt j \\leq N を満たす全ての組 (i,j)(i,j) について textdist(i,j)\\text{dist}(i,j) を求め、その総和を (109+7)(10^9+7) で割った余りを出力してください。

textXOR\\text{ XOR } とは

整数 a,ba, b のビットごとの排他的論理和 atextXORba \\text{ XOR } b は、以下のように定義されます。

  • atextXORba \\text{ XOR } b を二進表記した際の 2k2^k (kgeq0k \\geq 0) の位の数は、a,ba, b を二進表記した際の 2k2^k の位の数のうち一方のみが 11 であれば 11、そうでなければ 00 である。

例えば、3textXOR5=63 \\text{ XOR } 5 = 6 となります (二進表記すると: 011textXOR101=110011 \\text{ XOR } 101 = 110)。

制約

  • 2leqNleq2times1052 \\leq N \\leq 2 \\times 10^5
  • 1lequiltvileqN1 \\leq u_i \\lt v_i \\leq N
  • 0leqwilt2600 \\leq w_i \\lt 2^{60}
  • 与えられるグラフは木
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

NN u1u_1 v1v_1 w1w_1 u2u_2 v2v_2 w2w_2 vdots\\vdots uN1u_{N-1} vN1v_{N-1} wN1w_{N-1}

出力

textdist(i,j)\\text{dist}(i,j) の総和を (109+7)(10^9+7) で割った余りを出力せよ。


入力例 1

3
1 2 1
1 3 3

出力例 1

textdist(1,2)=1,\\text{dist}(1,2)=1, textdist(1,3)=3,\\text{dist}(1,3)=3, textdist(2,3)=2\\text{dist}(2,3)=2 であり、これらの総和は 66 です。


入力例 2

5
3 5 2
2 3 2
1 5 1
4 5 13

出力例 2

62

入力例 3

10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

出力例 3

241240228

(109+7)(10^9+7) で割った余りを出力してください。