区域赛练习题

时间限制: 4000 ms 内存限制: 131072 kb

总通过人数: 1 总提交人数: 1

题目描述

区域赛第 X 命题委员会有 $N$ 位成员，其中第 $i$ 个人出了 $A_i$ 道难题和 $B_i$ 道水题。现在委员会要从 $N$ 个人中选择两个人，将他们出的所有题目组成一套区域赛练习题。

定义两套题目相同当且仅当选出的两位出题人完全相同并且套题中两两对应的题目的难度完全相同，请问组成一套区域赛练习题一共有多少种不同的可能？答案可能很大，你只需要给出答案对 $10^9+7$ 取模的值。

例如两位出题人提供了 2 道难题和 2 道水题，则他们一共可以组成 6 种不同的区域赛练习题，分别是 (H,H,E,E), (H,E,H,E), (H,E,E,H), (E,E,H,H), (E,H,E,H), (E,H,H,E) ，其中 H 代表难题，E 代表水题。

第一行包含一个正整数 $T$ ，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含一个正整数 $N$ ，表示成员个数。

接下来 $N$ 行，第 $i$ 行包含两个非负整数 $A_i, B_i$ 。

保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。

$1 \leq T \leq 10, 1 < N < 10^5, 0 \leq A_i,B_i \leq 2000$

对于每组数据输出一行，包含一个整数，表示答案对 $10^9+7$ 取模后的结果。