题目描述

2202 年，人类的技术得到了极大的发展，安全、高速地传输信息也成为了发展中必 不可少的一环。

地球上现存 $k$ 个国家，他们准备联合起来建立包含 $n$ 个数据处理中心的，分布全球的大型数据处理基地。其中仅允许 $m$ 对数据处理中心之间进行双向数据传输，并且保证任意两个中心之间都可以直接或间接进行数据传输。接下来面临的问题就是 $k$ 个国家如何分配这 $n$ 个数据处理中心，使得每个数据处理中心都恰好属于一个国家。

把数据处理中心从 $1$ 到 $n$ 编号，把数据传输关系从 $1$ 到 $m$ 编号。为了保证数据传输的安全性与高效性，如果数据传输两端的中心属于两个不同的国家，那么必须采用加密传输方式，在第 $i$ 对数据传输关系中这样的方式有 $diff_i$ 种；否则必须采用明文传输方式，在第 $i$ 对数据传输关系中这样的方式有 $same_i$ 种。由于某些限制，$diff_i$ 或 $same_i$ 可能为 $0$（但不会同时为 $0$），表示无法找到合适的传输方式，那么这样的分配方案就不合理，他们不会选用。

现在，他们正在开会商讨分配方式。他们会先决定每个数据处理中心分配给哪一个国家，然后决定每一条传输关系选用何种传输方式——当然，必须是合法的。

你很想知道，究竟会有多少种不同的合理的分配方案呢？——两个方案不同，当且仅当存在一个数据处理中心（在两种方案中）所属的国家不同，或存在一条传输关系（在两 种方案中）选用了不同的传输方式。你只想知道所有方案的总数除以 $10^9+7$ 的余数。

输入格式

从文件 trans.in 中读入数据。

第一行一个整数 $T$，表示数据组数。

接下来是 $T$ 组数据，对于每组数据：

第一行包含三个整数 $n,m,k$ 表示数据传输中心的个数、数据传输关系的个数和国家的个数；

接下来 $m$ 行，每行四个整数 $x_i,y_i,diff_i,same_i$，表示数据传输关系两端的数据传输中心、在这种传输关系中的加密传输方式的数量和明文传输方式的数量。

输出格式

输出到文件 trans.out 中。 输出文件包含 $T$ 行，对于每组数据，输出一行一个整数，表示不同的合理方案个数除以 $10^9+7$ 的余数。

样例 1 输入

1
2 4 3
2 1 1 1
2 1 2 2
2 1 2 0
1 2 1 1

样例 1 输出

24

样例 1 解释

如果中心 $1$ 被国家 $1$ 占领，中心 $2$ 被国家 $1$ 占领，则方案数为 $1 \times 2 \times 0 \times 1 = 0$；

如果中心 $1$ 被国家 $1$ 占领，中心 $2$ 被国家 $2$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $1$ 占领，中心 $2$ 被国家 $3$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $2$ 占领，中心 $2$ 被国家 $1$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $2$ 占领，中心 $2$ 被国家 $2$ 占领，则方案数为 $1 \times 2 \times 0 \times 1 = 0$；

如果中心 $1$ 被国家 $2$ 占领，中心 $2$ 被国家 $3$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $3$ 占领，中心 $2$ 被国家 $1$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $3$ 占领，中心 $2$ 被国家 $2$ 占领，则方案数为 $1 \times 2 \times 2 \times 1 = 4$；

如果中心 $1$ 被国家 $3$ 占领，中心 $2$ 被国家 $3$ 占领，则方案数为 $1 \times 2 \times 0 \times 1 = 0$；

因此总方案数为 $(0 + 4 + 4 + 4 + 0 + 4 + 4 + 4 + 0) \bmod (10^9 + 7) = 24$。

样例 2

大样例

测试点约束

对于所有测试点，$1 \leq T \leq 100$，$1 \leq n,m \leq 100$，$1 \leq x_i, y_i \leq n$，保证任意两个中心之间都可以直接或间接进行数据传输，$1 \leq k \leq 10^9,0 \leq diff_i,same_i \leq 10^9,diff_i + same_i \geq 1$，所有数据随机生成。

每个测试点的具体限制见下表：