World Domination

Evil organizations that attempt to conquer the world are everywhere, regardless of age, east or west fiction, non-fiction, but what on earth did they try to conquer the world? I suddenly thought about that because I was also planning to conquer the world. The only reason I want to conquer the world is to show the world that I am the best in the field of robotics in the world. I'm not interested in the world after the conquest, and I don't mind giving it to dogs everywhere.

I regret to say that there are researchers who are considered to be better than me. The person has an idea. Whoever it is, Dr. Synchronous R in my school days. I admit his achievements, but I don't think he was better than that of mine. However, he was well received by the professors because he was saying something sloppy, such as using robots for peace. Although I missed the president, I'm actually much better.

A simple example of its excellence is the combat robot prepared for this world domination. Combat robots have their own weapons according to their characteristics, and the weapons are contained in chips, but this chip has strong compatibility. It's not just compatible with the developers' own other combat robots (that's already achieved by none other than Dr. R). The great thing about my chip is that it's also compatible with Dr. R's housework robot. The housework robot is a one-off model not for sale, so I developed a compatible chip without knowing the robot's design. I have to say that it is a divine work. Some people call this spec a wasteful spec for the enemy, but it's a silly idea. I'm developing a combat robot to show my excellence. It's not just about winning.

Let's return to the world domination plan. I built n combat robots, each with one different weapon chip installed. He intends to use it to seize the world's major facilities, but Dr. R will send in a robot to help with his housework to thwart the plan. The domestic help robot challenges my combat robot with its own weapon, but each battle takes a unit of time, and as a result of the battle, one of the robots is defeated and destroyed.

If my robot is destroyed as a result of a battle, the robot's weapon chips will be stolen by the opponent. The weapon chip of one of my robots is the weakness of one of my other robots, and every my robot has only one weakness of the weapon chip. For each of my robots, I can estimate the probability of defeat if the opponent has the weakness weapon of that robot and the probability of defeat if they do not.

If the opponent's housework robot is destroyed as a result of the battle, Dr. R will send the same housework robot through the spare body transfer system. At this time, the weapon chips already obtained by the opponent's robot are not lost. Dr. R uses the spare body transfer system indefinitely, but I can repair my combat robot in the meantime, so the probability of defeat described above does not change no matter how many times I fight. Also, the spare body transfer system can only be used where the housework robot was destroyed when it was destroyed, so the housework robot cannot challenge another of my combat robots immediately after being defeated.

It's only a matter of time before all n combat robots are destroyed, as Dr. R has unlimited spare body transfer systems. So, behind the scenes of fighting combat robots, I will work on developing more robots that can destroy the entire spare body transfer system. But how much time do I have left? How long would it take for Dr. R's robot to take the fastest strategy to destroy my n robots? You have to calculate it first. By the way, I would like to confirm how many such robots are defeated.

Input

The input consists of multiple cases. Each case is given in the following format.

n p0 id0 w0 p1 id1 w1 .. .. .. p1 idn-1 wn-1

pi represents the probability that the i-th combat robot will be defeated when the opponent does not have a weak weapon. idi represents a combat robot that has a weapon that is the weakness of the i-th combat robot. wi represents the probability that the i-th combat robot will be defeated when the opponent has a weak weapon.

The end of the input is given by n = 0.

Each value meets the following conditions 2 ≤ n ≤ 100 pi and wi are represented by numbers with three decimal places. 0.001 ≤ pi <wi ≤ 1.000 idi! = i

The number of test cases does not exceed 500.

Output

Output the expected value of the time until the n combat robots are destroyed and the remainder of dividing the number of combinations of the destruction order by 1000000007 with a blank. The expected value has an error of up to 1e-9 from the answer prepared by the judge.

Example

Input

4 0.200 3 0.500 0.100 0 0.400 0.900 1 1.000 0.400 2 0.600 2 0.600 1 0.800 0.500 0 1.000 9 0.200 7 0.600 0.400 0 0.500 0.700 8 1.000 0.100 4 0.400 0.200 2 0.600 0.100 6 0.400 0.100 5 0.400 0.600 3 0.900 0.500 1 0.900 9 0.300 8 0.900 0.700 3 0.800 0.300 0 0.900 0.700 6 0.800 0.200 5 0.700 0.200 2 0.700 0.700 4 0.800 0.700 1 0.800 0.300 7 0.900 0

Output

7.27777777778 1 2.66666666667 1 23.98412698413 72 11.36904761905 4

inputFormat

Input

The input consists of multiple cases. Each case is given in the following format.

n p0 id0 w0 p1 id1 w1 .. .. .. p1 idn-1 wn-1

pi represents the probability that the i-th combat robot will be defeated when the opponent does not have a weak weapon. idi represents a combat robot that has a weapon that is the weakness of the i-th combat robot. wi represents the probability that the i-th combat robot will be defeated when the opponent has a weak weapon.

The end of the input is given by n = 0.

Each value meets the following conditions 2 ≤ n ≤ 100 pi and wi are represented by numbers with three decimal places. 0.001 ≤ pi <wi ≤ 1.000 idi! = i

The number of test cases does not exceed 500.

outputFormat

Output

Output the expected value of the time until the n combat robots are destroyed and the remainder of dividing the number of combinations of the destruction order by 1000000007 with a blank. The expected value has an error of up to 1e-9 from the answer prepared by the judge.

Example

Input

4 0.200 3 0.500 0.100 0 0.400 0.900 1 1.000 0.400 2 0.600 2 0.600 1 0.800 0.500 0 1.000 9 0.200 7 0.600 0.400 0 0.500 0.700 8 1.000 0.100 4 0.400 0.200 2 0.600 0.100 6 0.400 0.100 5 0.400 0.600 3 0.900 0.500 1 0.900 9 0.300 8 0.900 0.700 3 0.800 0.300 0 0.900 0.700 6 0.800 0.200 5 0.700 0.200 2 0.700 0.700 4 0.800 0.700 1 0.800 0.300 7 0.900 0

Output

7.27777777778 1 2.66666666667 1 23.98412698413 72 11.36904761905 4

样例

4
0.200 3 0.500
0.100 0 0.400
0.900 1 1.000
0.400 2 0.600
2
0.600 1 0.800
0.500 0 1.000
9
0.200 7 0.600
0.400 0 0.500
0.700 8 1.000
0.100 4 0.400
0.200 2 0.600
0.100 6 0.400
0.100 5 0.400
0.600 3 0.900
0.500 1 0.900
9
0.300 8 0.900
0.700 3 0.800
0.300 0 0.900
0.700 6 0.800
0.200 5 0.700
0.200 2 0.700
0.700 4 0.800
0.700 1 0.800
0.300 7 0.900
0

7.27777777778 1
2.66666666667 1
23.98412698413 72
11.36904761905 4

</p>