Qingyu's Online Judge


Time Limit:2 s Memory Limit:1024 MB

#3006. Heaps of Fun


Problem Description

Consider a rooted tree with $n$ nodes, numbered $1 \cdots 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 \times Q^{-1} \bmod{(10^9+7)}$, where $Q^{-1}$ is an integer, which is the multiplicative inverse of $Q$ modulo $10^9+7$ ($Q \times Q^{-1} \equiv 1 \pmod{10^9+7}$). (Note: $P \times Q \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 \leq n \leq 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 \leq b \leq 10^9$) and $p$($0 \leq p\leq 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 \times Q^{-1} \bmod{(10^9+7)}$.


Sample Input 1

1000000000 0
1000000000 1

Sample Output 1


Sample Input 2

2 3
2 3
1 0
2 3
2 3

Sample Output 2