车如何移动？

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

你在一个 $n\times n$ 的棋盘上玩一个游戏。

每次你可以选择位置 $(r,c)$ 放置一个白色车，使放置后任意两辆车（无论颜色）都不能在同一行或同一列相互攻击。如果 $r\ne c$，电脑随后会在 $(c,r)$ 放置一个黑色车；只要你的操作合法，电脑的操作也一定合法。

现在你已经进行了 $k$ 次操作，输入给出这 $k$ 辆白色车的位置，电脑也已经完成了对应操作。之后你继续操作，直到棋盘上再也不存在合法位置。

求游戏结束时可能形成多少种不同局面。两个局面不同，当且仅当存在一个位置，其上的车的颜色不同，或仅有一个局面在该位置放有车。

答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $t$，表示数据组数。

对于每组数据，第一行包含两个整数 $n,k$。

接下来 $k$ 行，每行包含两个整数 $r_i,c_i$，表示第 $i$ 次操作放置的白色车的位置。输入保证这些操作均合法。

输出格式

对于每组数据，输出一行一个整数，表示可能的最终局面数对 $10^9+7$ 取模后的结果。

样例输入 1

3
4 1
1 2
8 1
7 6
1000 4
4 4
952 343
222 333
90 91

样例输出 1

3
331
671968183

数据范围

对于全部数据，$1\le t\le 10^4$，$1\le n\le 3\times 10^5$，$0\le k\le n$，$1\le r_i,c_i\le n$，且单个输入文件内满足 $\sum n\le 3\times 10^5$。