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}$.)

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 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 |