染色

题目描述

对 $n$ 个点与 $m$ 条边组成的连通图，保证无自环，但可能有重边。

对点和边进行染色。首先给定$k$种颜色，对每个点染这$k$种颜色之一。然后对每条边，第$i$条边如果两端点颜色相同，就有 $s a m e_{i}$ 种染色方式；如果两端颜色不同，就有 $d i f f_{i}$ 种染色方式。

求总染色方案数，对 $1 0^{9}+7$ 取模。两种染色不同，当且仅当有至少一个点颜色不同，或者有至少一条边采用了不同的染色方式。

输入格式

输入文件的第一行包含一个整数 $T$ ，表示数据的组数，接下来是 $T$ 组数据；

每组数据的第一行包含三个整数 $n, m, k$ ，表示点数、边数、颜色数；

接下来 $m$ 行，每行四个整数 $x_{i}, y_{i}, d i f f_{i}, s a m e_{i}$ ，表示第 $i$ 条边连接 $x_{i}, y_{i}$ 及其两端颜色相异、相同时的染色方式数。

输出格式

输出文件包含 $T$ 行，对于每组数据，输出一行一个整数，表示不同的染色方案个数除以 $1 0^{9}+7$ 的余数。

样例 1

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

24

样例一解释

按仅有的两个结点的染色方案分类：

染色情况为$(1, 1)$: $1 \times2 \times0 \times1=0$

染色情况为$(1, 2)$: $1 \times2 \times2 \times1=4$

染色情况为$(1, 3)$: $1 \times2 \times2 \times1=4$

染色情况为$(2, 1)$: $1 \times2 \times2 \times1=4$

染色情况为$(2, 2)$: $1 \times2 \times0 \times1=0$

染色情况为$(2, 3)$: $1 \times2 \times2 \times1=4$

染色情况为$(3, 1)$: $1 \times2 \times2 \times1=4$

染色情况为$(3, 2)$: $1 \times2 \times2 \times1=4$

染色情况为$(3, 3)$: $1 \times2 \times0 \times1=0$

因此总方案数为 $( 0+4+4+4+0+4+4+4+0 ) \bmod( 1 0^{9}+7 )=2 4$ 。

数据范围

本题共20个测试点。

下发大样例ex_D1到ex_D17依次符合测试点$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18$的限制。

更多样例

以下 17 组大样例取自原题附件：

• ex_D1.in / ex_D1.out
• ex_D2.in / ex_D2.out
• ex_D3.in / ex_D3.out
• ex_D4.in / ex_D4.out
• ex_D5.in / ex_D5.out
• ex_D6.in / ex_D6.out
• ex_D7.in / ex_D7.out
• ex_D8.in / ex_D8.out
• ex_D9.in / ex_D9.out
• ex_D10.in / ex_D10.out
• ex_D11.in / ex_D11.out
• ex_D12.in / ex_D12.out
• ex_D13.in / ex_D13.out
• ex_D14.in / ex_D14.out
• ex_D15.in / ex_D15.out
• ex_D16.in / ex_D16.out
• ex_D17.in / ex_D17.out