时间限制： 每个测试 $2$ 秒
内存限制： 每个测试 $256$ MB

心落河从命运之地中部横贯而过，将整片土地分为北岸和南岸。

工程师“根”想要沿河建造 $n$ 座房屋，编号从 $1$ 到 $n$。所有北岸的房屋必须沿一条平行于心落河的直线排列，所有南岸的房屋同样沿另一条平行于心落河的直线排列。

规划中将有 $m$ 座桥，第 $i$ 座桥连接房屋 $u_i$ 和房屋 $v_i$（$u_i \neq v_i$）。数据保证所有 $n$ 座房屋通过这些桥连通，即你可以通过过桥从任意一座房屋到达任意另一座房屋。此外，不存在两座桥连接同一对房屋。

根想知道，有多少种沿河排列这 $n$ 座房屋的方式（对 $10^9+7$ 取模），使得以下条件对规划的 $m$ 座桥全部成立：

• 对于每座桥，它所连接的两座房屋必须位于河的对岸；
• 当桥用直线段绘制时，桥与桥之间不能相交。

下图展示了 $n=5$ 时一种可能的房屋排列方案。

两种排列方式被视为不同，当且仅当以下至少一项成立：

• 存在某座房屋，在两种排列中位于河的不同侧；
• 存在两座房屋 $a$ 和 $b$，在两种排列中它们位于河的同一侧，但在一种排列中 $a$ 排在 $b$ 之前，而在另一种排列中 $b$ 排在 $a$ 之前。

因为根正被他那被命运拆散的前任所困扰，他请求你帮他计算合法的房屋排列方式的数量，结果对 $10^9+7$ 取模。

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$n-1 \le m \le \min\left(\frac{n(n-1)}{2}, 2\cdot 10^5\right)$）—— 房屋数量和桥的数量。

接下来 $m$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）—— 第 $i$ 座桥连接的两座房屋。

数据保证所有 $n$ 座房屋通过桥连通，且没有两座桥连接同一对房屋。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，$m$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出一个整数 —— 合法的房屋排列方式的数量，对 $10^9+7$ 取模。

样例输入

4
2 1
1 2
3 3
1 2
1 3
2 3
5 4
1 2
1 3
3 4
3 5
4 3
1 2
1 3
1 4

样例输出

2
0
8
12

提示
在第一个测试用例中，要么房屋 $1$ 建在北岸、房屋 $2$ 建在南岸，要么反过来。

在第二个测试用例中，至少有两座房屋必须建在河的同一侧。但每一对房屋之间都有桥相连，因此在任何排列中至少有一座桥不会跨过河流，违反了桥两端必须在不同侧的条件。故答案为 $0$。

在第三个测试用例中，题目描述里给出了一种可能的房屋排列方案。