$N$쌍의 이별한 커플이 새로운 인연을 찾기 위해 한자리에 모였다. 각 커플은 남자 $1$명과 여자 $1$명으로 구성되어 있으며, $N$쌍의 커플은 서로 다른 남자 $N$명과 서로 다른 여자 $N$명으로 구성되어 있다. 이들은 $1$번부터 $2N$번까지 번호가 붙은 $2N$개의 의자에 다음 조건을 만족하면서 앉아 있다. - 같은 의자에 앉은 다른 사람이 존재하지 않는다. 즉, 의자 $1$개에는 정확히 $1$명만 앉아 있다. - $i$번째 이별한 커플의 남자는 $L_i$번 의자, 여자는 $R_i$번 의자에 앉아 있다. $(1 \le i \le N)$ - $1 \le L_i < R_i \le 2N (1 \le i \le N)$ - $L_i < L_j < R_i < R_j$인 경우가 존재하지 않는다. $(1 \le i, j \le 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$개의 테스트케이스를 해결해야 한다. # 제약 조건 - 주어지는 모든 수는 정수이다. - $1 \le T \le 100$ - $1 \le N \le 3\,000$ - 각 테스트케이스의 모든 $N$의 합을 $S$라고 하면, $1 \le S \le 3\,000$ - $1 \le L_i < R_i \le 2N (1 \le i \le N)$ - $L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N$은 서로 다르다. - $L_i < L_j < R_i < R_j$인 경우가 존재하지 않는다. $(1 \le i, j \le N)$ # 부분문제 1. (11점) $N \le 8$, $S \le 800$. 2. (32점) $N \le 16$, $S \le 1\,600$. 3. (20점) $N \le 100$, $S \le 2\,000$, $L_i < L_j < R_j < L_k < R_k < R_i$인 경우가 존재하지 않는다. $(1 \le i, j, k \le N)$ 4. (27점) $N \le 100$, $S \le 2\,000$. 5. (10점) 추가 제약 조건 없음. # 입력 형식 첫 번째 줄에 테스트케이스의 개수 $T$가 주어진다. 두 번째 줄부터 $T$개의 테스트케이스가 주어진다. 각 테스트케이스는 $N+1$개의 줄로 구성되어 있다. 각 테스트케이스의 첫 번째 줄에 $N$이 주어진다. 각 테스트케이스의 $1+i$번째 줄에 $L_i$와 $R_i$가 공백으로 구분되어 주어진다. # 출력 형식 각 테스트케이스마다 한 줄에 하나씩 정답을 출력한다. # 예제 ## 예제 1 ### 입력 ``` 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 ```