問題文
N 頂点の重み付き木があります。i 本目の辺は頂点 ui と頂点 vi を双方向に結んでいて、その重みは wi です。
頂点の組 (x,y) について、textdist(x,y) を以下のように定めます。
- x から y への最短パスに含まれる辺全ての重みの XOR
1leqiltjleqN を満たす全ての組 (i,j) について textdist(i,j) を求め、その総和を (109+7) で割った余りを出力してください。
textXOR とは
整数 a,b のビットごとの排他的論理和 atextXORb は、以下のように定義されます。
- atextXORb を二進表記した際の 2k (kgeq0) の位の数は、a,b を二進表記した際の 2k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3textXOR5=6 となります (二進表記すると: 011textXOR101=110)。
制約
- 2leqNleq2times105
- 1lequiltvileqN
- 0leqwilt260
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
u1 v1 w1
u2 v2 w2
vdots
uN−1 vN−1 wN−1
出力
textdist(i,j) の総和を (109+7) で割った余りを出力せよ。
入力例 1
出力例 1
textdist(1,2)=1, textdist(1,3)=3, textdist(2,3)=2 であり、これらの総和は 6 です。
入力例 2
出力例 2
入力例 3
出力例 3
(109+7) で割った余りを出力してください。