题目描述

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 \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 \cdot Q^{-1}) \bmod (10^9+7)$.

2
1000000000 0
1000000000 1

500000004

5
2 3
2 3
1 0
2 3
2 

87500001