题目描述

A 国可以看成一棵 $n$ 个节点的树，小偷在 $1$ 号节点，而由于长时间的逃亡让小偷感到劳累，所以他会等概率随机选择某一个叶子节点，并沿着最短路径快速逃到那一个节点去休息。

在夜深人静的时候，警察决定将正在休息的小偷缉拿归案，一开始警察也在 $1$ 号节点，已知他经过每一条边都需要花费 $1$ 单位时间。

为了加快搜捕的进度，有一些节点上面安装了监控，警察可以通过这个监控来查清小偷是否曾经来过这个节点。由于警察经验丰富，他查监控的时间可以忽略不计。

同时为了防止扰民，警察会限制自己每条道路最多经过不超过 $2$ 次。

同时警察事先也知道小偷一定藏在某个叶子节点里，因为那里最容易逃出 A 国，为了防止小偷成功逃出 A 国，警察希望能尽快到达小偷所在的节点并抓住小偷，所以他想知道在期望情况下，至少需要花多长时间才能抓住小偷？由于答案可能不是整数，但可以证明一定是有理数，所以你只需要输出其对 $10^9+7$ 取模的结果即可，保证答案对 $10^9+7$ 取模是有意义的。

输入格式

第一行一个正整数 $n$。

第 $2$ 行至第 $n$ 行，第 $i$ 行一个正整数一个字符 $f_i,c_i$，其中 $f_i$ 代表 $i$ 和 $f_i$ 有连边，$c_i$ 代表该点是否有监控，若 $c_i=$ Y，则说明该点有监控；若 $c_i=$ N，则说明该点没有监控。

输出格式

共一行一个整数，代表答案对 $10^9+7$ 取模之后的结果。

输入样例 #1

5
1 N
1 Y
3 N
3 N

输出样例 #1

3

输入样例 #2

10
1 Y
1 N
2 N
2 N
2 N
3 N
3 Y
8 N
8 N

输出样例 #2

5

说明提示

【样例 #1 解释】

警察可以先到 $2$ 号节点，再到 $3$ 号节点（此时查监控已没有任何意义），然后再依次去 $4,5$ 号节点，期望时间为 $\dfrac{1+4+6}3=\dfrac{11}3$。

警察也可以选择先到 $3$ 号节点并查一下监控，如果小偷经过了 $3$ 号节点，那么小偷一定在 $4,5$ 号节点藏着，否则他一定在 $2$ 号节点藏着，警察可以根据此信息进一步搜查，期望时间为 $\dfrac{2+3+4}3=3$。

所以警察抓到小偷的期望最小时间为 $3$。

输入样例 #3

1

输出样例 #3

0

数据范围

对于全部测试点，满足 $1\le n\le 10^5,1\le f_i < i,c_i$ 只可能是 Y 或 N，每个测试点 $4$ 分。