Asteroid Field#1432
Vasya is creating a new space simulation game to gift to his friends. He devised the game concept, but the programming work was extensive, so he chose to delegate some tasks to his friends. You have been assigned the task related to asteroid fields.
Consider a space region that is units wide, where 1 < N \leq 10^9. A spaceship, which is units wide (1 < M \leq N), needs to cross this region. Asteroids, each occupying unit, are placed in a straight line across the region, meaning there are exactly possible positions for asteroids. The total number of asteroids, , does not exceed 10^6. The ship sustains minor damage if it collides with one asteroid, but takes critical damage requiring repairs if it hits at least two asteroids. The ship moves perpendicular to the line of asteroids and always crosses exactly potential asteroid positions. Your task is to determine the probability that the ship takes critical damage, given the arrangement of asteroids.
The first line contains three positive integers , , and , separated by spaces. The following lines each contain one positive integer, representing the positions of the asteroids (positions are numbered from to ).
Output the probability of the ship taking critical damage as an irreducible fraction. If the probability is or , output 0/1 or 1/1, respectively.
Example 1