60012 새로운 인연 Diamond V

문제

N쌍의 이별한 커플이 1번부터 2N번까지 번호가 붙은 의자에 앉아 있다. i번째 커플의 남자는 L_i번 의자, 여자는 R_i번 의자에 앉아 있으며, L_i < L_j < R_i < R_j인 경우가 존재하지 않는다.

다음 조건을 만족하는 N쌍의 새로운 커플을 만들어야 한다:

• 새로운 커플은 남자 1명과 여자 1명으로 구성
• 모든 사람은 정확히 1쌍에 속함
• 기존 이별한 상대와는 짝지어질 수 없음
• 남자의 의자 번호 < 여자의 의자 번호

조건을 만족하는 새로운 커플을 만드는 방법의 수를 10^9 + 7로 나눈 나머지를 구하시오.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)

각 테스트 케이스마다 첫 줄에 N, 다음 N줄에 L_i, R_i가 주어진다. (1 ≤ N ≤ 3,000, 모든 N의 합 ≤ 3,000)

출력

각 테스트 케이스마다 답을 출력한다.

5
1
1 2
2
1 4
2 3
3
1 6
2 5
3 4
3
1 6
2 3
4 5
4
1 8
5 6
2 7
3 4

0
1
2
1
6