60012 새로운 인연 Diamond V

문제

$N$쌍의 이별한 커플이 새로운 인연을 찾기 위해 한자리에 모였다. 각 커플은 남자 $1$명과 여자 $1$명으로 구성되어 있으며, $N$쌍의 커플은 서로 다른 남자 $N$명과 서로 다른 여자 $N$명으로 구성되어 있다. 이들은 $1$번부터 $2N$번까지 번호가 붙은 $2N$개의 의자에 다음 조건을 만족하면서 앉아 있다.

• 같은 의자에 앉은 다른 사람이 존재하지 않는다. 즉, 의자 $1$개에는 정확히 $1$명만 앉아 있다.
• $i$번째 이별한 커플의 남자는 $L_i$번 의자, 여자는 $R_i$번 의자에 앉아 있다. ($1 ≤ i ≤ N$)
• $1 ≤ L_i < R_i ≤ 2N$ ($1 ≤ i ≤ N$)
• $L_i < L_j < R_i < R_j$인 경우가 존재하지 않는다. ($1 ≤ i, j ≤ N$)

이들은 다음 조건을 만족하는 $N$쌍의 새로운 커플을 만들려고 한다.

• 새로운 커플은 남자 $1$명과 여자 $1$명으로 구성되어야 하며, 모든 사람은 정확히 $1$쌍의 새로운 커플에 속해야 한다.
• 모든 사람은 기존 이별한 상대가 아닌 사람과 짝지어져야 한다.
• 임의의 새로운 커플에 대해, 남자가 앉은 의자의 번호를 $l$, 여자가 앉은 의자의 번호를 $r$이라고 하면 $l < r$ 이다.

예를 들어, $N = 3$이고 $L_1 = 1$, $R_1 = 6$, $L_2 = 2$, $R_2 = 3$, $L_3 = 4$, $R_3 = 5$인 경우를 생각해 보자. $1$번 의자에 앉은 남자와 $6$번 의자에 앉은 여자는 이별한 커플이므로, 새로운 커플이 될 수 없다. $4$번 의자에 앉은 남자와 $3$번 의자에 앉은 여자는 이별한 커플이 아니지만, 남자가 앉은 의자의 번호가 더 크기 때문에 새로운 커플이 될 수 없다.

반면, $1$번 의자에 앉은 남자와 $3$번 의자에 앉은 여자는 새로운 커플이 될 수 있다. $2$번 의자에 앉은 남자와 $5$번 의자에 앉은 여자, $4$번 의자에 앉은 남자와 $6$번 의자에 앉은 여자도 새로운 커플이 될 수 있다. 이러한 방식으로 조건을 만족하는 $3$쌍의 커플을 만들 수 있다.

여러분은 $N$쌍의 새로운 커플을 만드는 서로 다른 방법의 수를 계산해야 한다. $N$쌍의 새로운 커플을 만드는 두 방법이 다르다는 것은 둘 중 하나로만 만들어질 수 있는 새로운 커플이 존재한다는 것을 뜻한다.

위에서 든 예시의 경우, $3$쌍의 커플을 만드는 방법이 유일하다는 것을 증명할 수 있다. 따라서, 이 경우 답은 $1$이다.

방법의 수가 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 구하여라.

하나의 입력에서 $T$개의 테스트케이스를 해결해야 한다.

입력

첫 번째 줄에 테스트케이스의 개수 $T$가 주어진다.

두 번째 줄부터 $T$개의 테스트케이스가 주어진다. 각 테스트케이스는 $N + 1$개의 줄로 구성되어 있다.

각 테스트케이스의 첫 번째 줄에 $N$이 주어진다.

각 테스트케이스의 $1 + i$번째 줄에 $L_i$와 $R_i$가 공백으로 구분되어 주어진다.

출력

각 테스트케이스마다 한 줄에 하나씩 정답을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ T ≤ 100$
• $1 ≤ N ≤ 3\, 000$
• 각 테스트케이스의 모든 $N$의 합을 $S$라고 하면, $1 ≤ S ≤ 3\, 000$
• $1 ≤ L_i < R_i ≤ 2N$ ($1 ≤ i ≤ N$)
• $L_1 ,L_2 ,\cdots ,L_N , R_1 , R_2 , \cdots, R_N$은 서로 다르다.
• $L_i < L_j < R_i < R_j$ 인 경우가 존재하지 않는다. ($1 ≤ i, j ≤ N$)

서브태스크

번호	배점	제한
1	11	$N ≤ 8$, $S ≤ 800$.
2	32	$N ≤ 16$, $S ≤ 1\, 600$.
3	20	$N ≤ 100$, $S ≤ 2\, 000$, $L_i < L_j < R_j < L_k < R_k < R_i$인 경우가 존재하지 않는다. ($1 ≤ i, j, k ≤ N$)
4	27	$N ≤ 100$, $S ≤ 2\, 000$.
5	10	추가 제약 조건 없음.

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