High-Speed Railway

A high-speed railway test track can be represented as a straight line. Several robots are installed on the track, and each robot is responsible for one continuous inspection interval. If the inspection intervals of two robots overlap, those two robots must exchange a large amount of data, so at least one of them must be equipped with a special data-processing device.

Suppose there are four robots a, b, c, and d as shown below. The intervals of a and b overlap, so at least one of them needs the device. The same condition must also hold for b and c, b and d, and c and d.

There may be many valid ways to attach the devices. In the figure above, attaching devices to all four robots is valid, and attaching them only to b and c is also valid. The seven valid choices are {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {b, d}, and {b, c}.

Given the inspection intervals of the robots, write a program that counts the number of ways to attach devices so that for every overlapping pair of robots, at least one of the two has a device.

The first line contains the number of robots N. (1 <= N <= 100,000)

Each of the next N lines contains two integers: the left endpoint and the right endpoint of one robot's inspection interval.

All coordinates are integers between 0 and 10,000,000, inclusive. The left endpoint of every interval is smaller than its right endpoint. All interval endpoint coordinates are distinct.

Print the number of valid ways to attach the data-processing devices.

If the number of ways is at least 20,070,713, print its remainder after division by 20,070,713. Be careful that overflow may occur during the calculation.