The Lion King

In the Pride Lands of Africa, a lion rules over the animals as king. The birth of King Mufasa and QueenSarabi’s son Simba creates envy and resentment in Mufasa’s younger brother, Scar, who knows his nephewnow replaces him as heir to the throne.

After Simba has grown into a young cub, Mufasa gives him a tour of the Pride Lands, teaching him theresponsibilities of being a king and the circle of life. They spent the whole day in this tour and now it’stime to sleep.

As Simba is still young, he didn’t manage to sleep quickly and kept nudging his father to speak with him.Mufasa is really tired and would like to sleep so he thought of asking Simba a hard question to keep himbusy. Mufasa asked Simba how many stars are there in the sky?

Simba sees the sky as an infinite 2D grid with some glowing points.

A star is a set of ve points (p1, p2, p3, p4, and p5) satisfying these conditions:

• p1.y > p5.y

• p5.y = p2.y

• p3.y, p4.y < p5.y

• p5.x < p1.x < p2.x

• p5.x < p4.x < p1.x

• p1.x < p3.x < p2.x

Can you help Simba answer this question as soon as possible?

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integerT, the number of test cases (1 ≤ T ≤ 200), followed by T test cases. The first line of each test case willcontain one integer N (5 ≤ N ≤ 5, 000) where N is the number of points in the sky.

The following N lines will each contain a pair of integers x and y separated by a single space(( -5, 000 ≤ x, y ≤ 5, 000) representing the coordinates of the points.

Output

For each test case, print one line which contains the number of stars that Simba can see in the sky modulo1,000,000,007. Each point can belong to multiple stars.

样例输入
2
5
0 5
4 4
-4 4
2 0
-2 0
8
0 5
4 4
-6 4
2 0
-1 0
-5 4
0 12
3 0
样例输出
1
8

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;

const int ad = 5001, mod = 1e9 + 7;
typedef long long ll;
map<int, vector<int> > p;
map<int, vector<int> >::iterator it, it1;
set<int> xs;
set<int>::iterator it2;
map<pair<int, int>, ll> rc1, rc;
int T, n;
int x, y;

int main() {
    scanf("%d", &T);
    while (T--) {
        p.clear();
        xs.clear();
        rc.clear();
        rc1.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            p[y].pb(x), xs.insert(x);
        }
        for (it = p.begin(); it != p.end(); it++)
            sort((*it).se.begin(), (*it).se.end());
        for (it = p.begin(); it != --p.end(); it++) {
            int temp1 = (*(++it)).fi;
            it--;
            for (int i = 1; i <= (*it).se.size(); i++) {
                for (it2 = xs.begin(); it2 != xs.end(); it2++) {
                    if ((*it2) > (*it).se[i - 1])rc[{(*it2) + ad, temp1}]++;
                    if ((*it2) >= (*it).se[i - 1])rc1[{(*it2) + ad, temp1}]++;
                }
            }
            for (it2 = xs.begin(); it2 != xs.end(); it2++) {
                rc[{(*it2) + ad, temp1}] += rc[{(*it2) + ad, (*it).fi}];
                rc1[{(*it2) + ad, temp1}] += rc1[{(*it2) + ad, (*it).fi}];
            }
        }
        ll res = 0, cl = 0, cr = 0;
        it = p.end();
        it--;
        for (; it != ++p.begin(); it--) {
            for (int i = 1; i <= (*it).se.size(); i++) {
                cl = 0, cr = 0;
                it1 = (--it);
                it++;
                for (; it1 != p.begin(); it1--) {
                    for (int j = 1; j <= (*it1).se.size(); j++) {
                        if ((*it1).se[j - 1] < (*it).se[i - 1])
                            cl = (cl + rc[{(*it).se[i - 1] + ad, (*it1).fi}] -
                                  rc1[{(*it1).se[j - 1] + ad, (*it1).fi}]) % mod;
                        else if ((*it1).se[j - 1] > (*it).se[i - 1])
                            cr = (cr + rc[{(*it1).se[j - 1] + ad, (*it1).fi}] -
                                  rc1[{(*it).se[i - 1] + ad, (*it1).fi}]) % mod;
                    }
                    res = (res + cl * cr % mod) % mod;
                }
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}