새로운 인연 timer 2s memory 1024MB

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