The time has finally come for the last battle between The HERO and The DARK LORD!!! But sadly in this story, you are neither the Hero nor the Dark Lord. You are a programmer in the legion of the Dark Lord whose job is to calculate the probability of the Hero killing the Dark Lord. It may seem a simple task, but it is of great importance!
The Dark Lord resides within a castle which has the shape of a convex polygon made of black magic pillars. If the Hero can somehow manage to get the Dark Lord strictly out of the convex polygon shaped castle (which means not even on the boundary), then he (Hero) can kill him (Dark Lord). The pillars are numbered from 1 to in counter-clockwise order. The Hero has a special ability. If the power of the Hero's ability is , then if he chooses some pillar numbered i, he can destroy pillars starting from the pillar numbered . That is, he can destroy pillars numbered from to .
However DARK the Dark Lord is, he is scared of death too! So, he will try to remain in a place inside the castle so that the Hero can't kill him. But sometimes he just can't hide from the Hero's ability. The Hero also desperately wants to kill the Dark Lord so he too chooses the starting pillar wisely. But in some cases, he also can't kill the Dark Lord.
Before the battle starts, the power of the Hero's ability is decided by the two faced snake. The snake randomly chooses an integer between 1 and (both inclusive) and assigns the power of the Hero's ability to it.
Now, given that the power is chosen randomly and the Hero and the Dark Lord fights optimally, what is the probability of the Dark Lord surviving? Your job is to find that out.
At first line an integer will be given, the number of black magic pillars. For the next lines, a pair of integers and will be provided in each line , the co-ordinate of the -th black magic pillar. The points will be given in counter clockwise order.
Here, and .
Output the result in format , , are co-prime with each other. And in case the answer is 0, output .
Input | Output |
---|---|
4 1 1 6 1 6 6 1 6 | 1/2 |