\(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\)개의 테스트케이스를 해결해야 한다.

• 주어지는 모든 수는 정수이다.
• \(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\))

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

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

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

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

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 고등부 2번