Score : 600 points
We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.
For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:
Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.
Input is given from Standard Input in the following format:
N x_1 y_1 : x_N y_N
Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.
3 -1 3 2 1 3 -2
13
Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:
The sum of these is 13.
4 1 4 2 1 3 3 4 2
34
10 19 -11 -3 -12 5 3 3 -15 8 -14 -9 -20 10 -9 0 2 -7 17 6 -6
7222
Be sure to print the sum modulo 998244353.