Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P175PROC - ROUND 5C - Tô màu

Mật là một người rất thích cây. Một hôm, Mật được tặng một cái cây – cây là một đồ thị liên thông có N đỉnh và N-1 cạnh, cậu quyết định tô màu đỏ và đen cho các cạnh của cây. Sau khi tô màu, Mật tò mò muốn đếm xem có bao nhiêu bộ 3 đỉnh a,b,c thỏa mãn đường đi giữa 2 đỉnh bất kì luôn có ít nhất 1 cạnh có màu đỏ. Các hoán vị của (a,b,c) cũng chỉ được tính là 1 bộ 3 số thỏa mãn. Do cây quá to nên Mật không thể đếm nhanh được, các bạn hãy giúp Mật đếm xem có bao nhiêu bộ 3 đỉnh thỏa mãn nhé.

Input

Dòng đầu gồm số N là số đỉnh của cây (N<=10^5)

N-1 dòng tiếp theo, mỗi dòng chứa 2 số u,v và kí tự c

Nếu kí tự c là r nghĩa là cạnh u-v có màu đỏ.

Nếu kí tự c là b nghĩa là cạnh u-v có màu đen.

Output

Kết quả bài toán module (10^9+7)

Example

Input:
5
1 2 r
2 3 b
3 4 b
4 5 r
Output:
3

Giải thích: 3 bộ đỉnh thỏa mãn là (1,2,5), (1,3,5), (1,4,5)


Được gửi lên bởi:adm
Ngày:2017-03-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.