众所周知，北京理工大学（BIT）有两位 ACM 大神，分别叫 foreverlasting 和 fried-chicken。他们各自沉浸在完美的爱情中。以下链接讲述了 fried-chicken 的爱情故事： https://www.zhihu.com/question/62332494/answer/3076483871

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

Pedestrian1 想知道在“fried-chicken”图中存在多少个“foreverlasting”图。

上图定义了一个“foreverlasting”图。

请注意，如果两个“foreverlasting”图所构成的边集中至少有一条边不同，则认为这两个“foreverlasting”图是不同的。

换句话说，给定图为 $G(V, E)$。你需要计算满足以下条件的子图 $G'(V', E')$（其中 $V' \subseteq V, E' \subseteq E$）的数量： $V' = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8\}$， $E' = \{(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 \le T \le 10$)，表示测试用例的数量。接下来是各测试用例的描述。

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

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示一条连接节点 $u_i$ 和 $v_i$ 的边。

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

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

输出格式

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

样例

输入格式 1

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

输出格式 1

1