Lõppvooru kutsumine

시간 제한1.5초메모리 제한1024 MB

요약

각 학생이 두 시험 중 적어도 하나에서 다른 모든 학생보다 높은 점수를 받는 부분집합의 수를 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

On teatud arv õpilasi, kellest mõned tuleks informaatikaolümpiaadi lõppvooru kutsuda. Iga õpilase kohta on teada tema tulemus eelvoorus ja tema tulemus lahtisel võistlusel. Lõppvooru kutsumiseks on ainult üks reegel: iga kutsutud õpilane peab olema igast kutsumata õpilasest vähemalt ühel võistlusel rohkem punkte saanud. Informaatikaolümpiaadi žüriid huvitab, mitu erinevat võimalust on õpilaste lõppvooru kutsumiseks. Et lõppvoor saaks toimuda, tuleb võistlusele kutsuda vähemalt üks õpilane.

입력

Selles ülesandes võib sisend koosneda mitmest alamtestist. Sisendi esimesel real on alamtestide arv $T \le 100$ .

Iga alamtesti esimesel real on kõigi õpilaste arv ( $1 \le N \le 200\\,000$ ). Järgmisel $N$ real on igaühel kaks tühikuga eraldatud mittenegatiivset täisarvu, ühe õpilase punktid vastavalt eelvoorus ja lahtisel võistlusel.

Õpilaste arvude summa kõikide alamtestide peale kokku on maksimaalselt $200\\,000$ . Ükski õpilane ei saanud kummalgi võistlusel rohkem kui $1\\,000\\,000\\,000$ punkti.

출력

Iga alamtesti kohta väljastada eraldi reale üks täisarv: kutsumise võimaluste arvu jääk jagamisel arvuga $1\\,000\\,000\\,007$ . Vastused tuleb anda alamtestides sisendis andmise järjekorras.

예제2

예제 1
입력
```
1
4
40 10
10 10
20 30
20 10
```
예상 출력
```
5
```

예제 2

입력

3
4
5 0
0 0
5 0
10 0
4
100000000 100000000
100000000 1000000000
1000000000 100000000
1000000000 1000000000
6
0 1
1 0
2 1
3 0
4 1
4 0

예상 출력

3
5
11