题目描述

众所周知，BIT 有两位 ACM 传奇人物，名为 foreverlasting 和 fried-chicken，他们各自沉浸在美好的爱情中。fried-chicken 的爱情故事

Pedestrian1 喜欢图和数学。他需要你的帮助来解决一个简单的问题。你会得到一个名为 "fried-chicken" 的简单无向图，它有 $n$ 个节点和 $m$ 条边。请注意，该图不一定是连通的。节点编号从 1 到 $n$。

Pedestrian1 想知道在 "fried-chicken" 图中有多少个 "foreverlasting" 子图。

上图定义了一个 "foreverlasting" 图。

请注意，两个 "foreverlasting" 子图被认为是不同的，当构成这两个 "foreverlasting" 子图的边集中至少有一条边不同时。

换句话说，给定图 $G(V,E)$。你需要计算满足以下条件的子图 $G^{\prime}(V^{\prime},E^{\prime})$（$V^{\prime} \subseteq V, E^{\prime} \subseteq E$）的数量： $V^{\prime} = \{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7},v_{8}\}$ $E^{\prime} = \{(v_{1},v_{3}),(v_{2},v_{3}),(v_{3},v_{4}),(v_{3},v_{5}),(v_{3},v_{6}),(v_{3},v_{7}),(v_{4},v_{8}),(v_{5},v_{8}),(v_{6},v_{8}),(v_{7},v_{8})\}$

由于答案可能非常大，Pedestrian1 想知道答案对 $1000000007$ 取模的结果。

输入格式

输入的第一行包含整数 $T$（$1 \leq T \leq 10$），表示测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000, m \leq \frac{n(n - 1)}{2}$）——分别表示节点数和边数。

接下来的 $m$ 行，每行包含一条边的描述。每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n, u_i \neq v_i$）——一条连接节点 $u_i$ 和节点 $v_i$ 的边。

保证没有两条边连接同一对无序节点。

此外，保证所有测试用例的 $n$ 之和不超过 $3000$。

输出格式

对于每个测试用例，输出一个整数，表示答案对 $1000000007$ 取模的结果。

1
8 10
1 2
1 3
1 4
1 5
1 6
1 7
8 4
8 5
8 6
8 7

1