시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB16101066.667%

문제

Consider a rooted tree with n nodes, numbered 1..n. Each node will have a fixed integer b, and for each, a uniform random real number is chosen in the interval [0..b].

What is the probability that the random numbers chosen cause the tree to form a Heap (i.e., the random value in each node is less than the random values in its children)?

This probability can always be expressed as a rational number P/Q , with Q ≠ 0 (mod 109+7). You are to output the probability as P·Q−1 mod 109+7, where Q−1 is an integer, which is the multiplicative inverse of Q modulo 109+7 (Q·Q−1 ≡ 1 (mod 109+7)). (Note: P·Q−1 mod 109+7 does not depend on whether P and Q are relatively prime, only on their ratio P/Q.)

입력

Each test case will begin with a line with a single integer n (1 ≤ n ≤ 300), which is the number of nodes in the tree.

Each of the next n lines will contain a pair of space-separated integers b (1 ≤ b ≤ 109) and p (0 ≤ p ≤ n) describing a node of the tree, where b is the fixed integer value in the node and p is the node number of its parent. The nodes are listed in order; node 1 is first, then node 2, and so on. A single node will have a parent p=0. This is the root of the tree.

출력

Output a single integer, which is the probability expressed as (P·Q−1) mod (109+7).

예제 입력 1

2
1000000000 0
1000000000 1

예제 출력 1

500000004

예제 입력 2

5
2 3
2 3
1 0
2 3
2 3

예제 출력 2

87500001