← 返回题目列表

AtCoder · icpc2012autumn_j

I. 桥乡大人

中文机器翻译题面 查看原题

问题陈述

切尔西是一位现代艺术家。她决定用梯子来做她的下一个工作。她想组合一些梯子并画出一些美丽的图案。

梯子可以被认为是一个称为 桥乡。有 给出了 n 桥五 编号从 0 到 n-1. 桥乡 i 长度 l_i 有 当以二进制形式写入时,位于 2 l_{i} + 6 顶点 v_{i, 0}, v_{i, 1}, ..., v_{i, 2 l_{i} + 5} 并且在一对顶点之间有边 (v_{i, j}, v_{i, j+2}) (0 \leq j \leq 2 l_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}).

切尔西执行此操作 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