Consider a rooted tree with nodes, numbered . Each node will have a fixed integer , and for each, a uniform random real number is chosen in the interval .
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 , with . You are to output the probability as , where is an integer, which is the multiplicative inverse of modulo (). (Note: does not depend on whether and are relatively prime, only on their ratio .)
输入格式
Each test case will begin with a line with a single integer (), which is the number of nodes in the tree.
Each of the next lines will contain a pair of space-separated integers () and () describing a node of the tree, where is the fixed integer value in the node and 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 . This is the root of the tree.
输出格式
Output a single integer, which is the probability expressed as .
