Hide

Problem F
Heaps of Fun

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 $\frac{P}{Q}$, with $Q{\not\equiv }0 \pmod{10^9{+}7}$. You are to output the probability as $P{\cdot }Q^{-1} \bmod {10^9{+}7}$, where $Q^{-1}$ is an integer, which is the multiplicative inverse of $Q$ modulo $10^9{+}7$ ($Q\! \cdot \! Q^{-1}\! \equiv \! 1 \pmod{10^9{+}7}$). (Note: $P{\cdot }Q^{-1}\bmod {10^9{+}7}$ does not depend on whether $P$ and $Q$ are relatively prime, only on their ratio $\frac{P}{Q}$.)

Input

Each test case will begin with a line with a single integer $n$ ($1\! \le \! n\! \le \! 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\! \le \! b\! \le \! 10^9$) and $p$ ($0\! \le \! p\! \le \! 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

Output a single integer, which is the probability expressed as $(P{\cdot }Q^{-1}) \bmod ({10^9{+}7})$.

Sample Input 1 Sample Output 1
2
1000000000 0
1000000000 1
500000004

Sample Input 2 Sample Output 2
5
2 3
2 3
1 0
2 3
2 3
87500001

Please log in to submit a solution to this problem

Log in