QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#3006. Heaps of Fun

Statistics

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

Input

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

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

Samples

Sample Input 1

2
1000000000 0
1000000000 1

Sample Output 1

500000004

Sample Input 2

5
2 3
2 3
1 0
2 3
2 3

Sample Output 2

87500001