QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB
[+2]

# 3006. Heaps of Fun

Statistics

Problem Description

Consider a rooted tree with n nodes, numbered 1n. 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 PQ, 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