问题陈述

Chelsea是一位现代艺术家。她决定用梯子制作她的下一个作品。她想要组合一些梯子，并绘制出一些漂亮的图案。

一个梯子可以被看作是一个叫做“哈希戈（hashigo）”的图形。有 $n$ 个编号为从 0 到 $n-1$ 的哈希戈。长度为 $l_i$ 的哈希戈有 $2l_i+6$ 个顶点 $v_{i,0}, v_{i,1}, ..., v_{i,2l_i+5}$，并且在顶点对 $(v_{i,j},v_{i,j+2})$ ($0 \leq j \leq 2l_i+3$) 和 $(v_{i,2j},v_{i,2j+1})$ ($1 \leq j \leq l_i+1$) 之间有边。下面是一个长度为2的哈希戈的示例。这对应于样例输入中第一个数据集中给出的图形。

两个哈希戈 $i$ 和 $j$ 在位置 $p$ ($0 \leq p \leq l_{i}-1$) 和 $q$ ($0 \leq q \leq l_{j}-1$) 处通过合并每对顶点 $(v_{i,2p+2},v_{j,2q+2})$，$(v_{i,2p+3},v_{j,2q+4})$，$(v_{i,2p+4},v_{j,2q+3})$ 和 $(v_{i,2p+5},v_{j,2q+5})$ 来进行组合。

Chelsea将这个操作执行 $n-1$ 次，以组合这 $n$ 个哈希戈。在此操作之后，图形应该是连通的，并且图形的最大度数不应超过4。下面是通过组合三个哈希戈得到的图形的示例。这对应于样例输入中第二个数据集中给出的图形。

现在她决定为每个顶点选择黑色或白色，同时满足以下条件：

• 连接顶点按相同颜色绘制时所形成的最大连通分量数小于或等于 $k$。

她想要尝试所有的图案并选择最好的。然而，绘制的方式数量可能非常庞大。由于她不擅长数学和计算，无法计算数量。所以请使用你的卓越编程技能帮助她！

输入

输入包含多个数据集，每个数据集的格式如下。

$n$ $k$ $l_0$ $l_1$ ... $l_{n-1}$ $f_0$ $p_0$ $t_0$ $q_0$ ... $f_{n-2}$ $p_{n-2}$ $t_{n-2}$ $q_{n-2}$

第一行包含两个整数 $n$ ($1 \leq n \leq 30$) 和 $k$ ($1 \leq k \leq 8$)。

接下来的一行包含 $n$ 个整数 $l_i$ ($1 \leq l_i \leq 30$)，表示哈希戈 $i$ 的长度。

接下来的 $n-1$ 行，每行包含四个整数 $f_i$ ($0 \leq f_i \leq n-1$)，$p_i$ ($0 \leq p_i \leq l_{f_i}-1$)，$t_i$ ($0 \leq t_i \leq n-1$)，$q_i$ ($0 \leq q_i \leq l_{t_i}-1$)。它表示哈希戈 $f_i$ 和哈希戈 $t_i$ 在位置 $p_i$ 和位置 $q_i$ 处进行组合。你可以假设通过组合 $n$ 个哈希戈得到的图形是连通的，并且图形的每个顶点的度数都不超过4。

最后一个数据集后面是一行包含两个零。

输出

对于每个数据集，在一行中打印不同着色方案的数量，模 1,000,000,007。

样例输入

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

样例输入对应的输出

708
1900484
438404500
3878
496
14246
9768

资源名称

JAG Practice Contest for ACM-ICPC Asia Regional 2012