John Doe has n line segments. Segment (a, b) (a < b) — is the set of points x such that a < x < b. Segments (a1, b1) and (a2, b2) are said to intersect if there exists a point c such that a1 < c < b1 and a2 < c < b2.
John wants to color each segment black or white so that no two segments of the same color intersect. He wants to know how many different ways there are to color the segments in this way.
Two colorings are considered different if there is a segment that is white in one coloring and in the other — to black.
Let the number of ways to color the segments be x. Print the remainder of x divided by 106 + 3.
Input
The first line contains an integer n (1 ≤ n ≤ 105) — John's number of segments. The next n lines contain the description of the segments. The i-th of them contains two numbers li and ri (0 ≤ li < ri ≤ 109) — coordinates of the ends of the i-th segment.
Output
Print the remainder after dividing x (the number of ways to color the segments) by 106 + 3.
Test examples
Input
Input data
4
12
2 3
3 4
4 5
Note
Tests are divided into groups, but are evaluated separately.
-
n ≤ 3 — 10 points
-
n ≤ 15 — 30 points
-
n ≤ 100 — 20 points
-
ai ≤ 106 — 20 points
-
Without additional restrictions — 20 points