问题陈述
切尔西是一位现代艺术家。她决定用梯子来做她的下一个工作。她想组合一些梯子并画出一些美丽的图案。
梯子可以被认为是一个称为 桥乡。有 给出了 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