#abc136f. [abc136_f]Enclosed Points
[abc136_f]Enclosed Points
Problem Statement
We have a set of points in a two-dimensional plane. The coordinates of the -th point are . The points have distinct -coordinates and distinct -coordinates.
For a non-empty subset of , let be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in . More formally, we define as follows:
- (the number of integers such that and , where , , , and are the minimum -coordinate, the maximum -coordinate, the minimum -coordinate, and the maximum -coordinate of the points in )
Find the sum of over all non-empty subset of . Since it can be enormous, print the sum modulo .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the sum of over all non-empty subset of , modulo .
Sample Input 1
3
-1 3
2 1
3 -2
Sample Output 1
13
Let the first, second, and third points be , , and , respectively. has seven non-empty subsets, and has the following values for each of them:
The sum of these is .
Sample Input 2
4
1 4
2 1
3 3
4 2
Sample Output 2
34
Sample Input 3
10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6
Sample Output 3
7222
Be sure to print the sum modulo .