34205번 - 새로운 인연 서브태스크

문제

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

• 같은 의자에 앉은 다른 사람이 존재하지 않는다. 즉, 의자 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$)

서브태스크

힌트