CPFED (Competitive Programming Federation) федерациясы \(N\) серверден тұратын шифрланған байланыс желісін басқарады. Бұл серверлердің арасындағы байланыстар шифрлау кілті ретінде қарастырылатын \(w_i\) салмақтары бар және олар ағаш (tree) құрылымын құрайды.

Әрбір байланыс екі бағытта жұмыс істейді және қауіпсіз. Бірақ екі сервер \((x, y)\) арасында дерек жіберу кезінде, олардың арасындағы ең қысқа жолдағы барлық қабаттардың салмақтарының XOR операциясы орындалады. Бұл — екі сервер арасындағы ерекше XOR-қашықтық болып табылады.

XOR-қашықтық деген не? Берілген екі сервер \(x\) және \(y\) үшін олардың XOR-қашықтығы — оларды байланыстыратын ең қысқа жолдағы барлық қабаттардың салмақтарының XOR-ы:

\(dist(x, y) = w_1 \oplus w_2 \oplus \dots \oplus w_k\)

мұндағы \(\oplus\) — бұл биттік XOR (немесе "қосымша ИЛИ") операциясы.

Мысал:

- Салмақтары \(w_1 = 1\), \(w_2 = 3\) және \(w_3 = 4\) болатын шеттері бар екі сервер арасындағы жол болсын. Сонда осы серверлер арасындағы XOR қашықтығы: Егер \(w_1 = 1\), \(w_2 = 3\), \(w_3 = 4\) болса, онда:

\(dist(x, y) = 1 \oplus 3 \oplus 4 = 6\)

Тапсырма: Барлық \((i, j)\) жұптары үшін (\(1 \le i < j \le N\)) XOR-қашықтықтарын есептеп, олардың қосындысын \(10^9 + 7\) бойынша модульмен шығару керек.

Енгізу

Бірінші жолда \(N\) (\(2 \le N \le 2 \cdot 10^5\)) — серверлер саны.

Келесі \(N - 1\) жолда үш бүтін саннан тұратын \(u_i\), \(v_i\), \(w_i\) (\(1 \le u_i, v_i \le N\), \(0 \le w_i < 2^{60}\)) — \(u_i\) және \(v_i\) серверлерін байланыстыратын қабат және оның XOR салмағы.

Берілген граф — ағаш екені кепілдендірілген.

Шығару

Барлық \((i, j)\) жұптарының XOR-қашықтықтарының қосындысын \(10^9 + 7\) бойынша шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

3
1 2 1
2 3 2

Жауап 1

6