Hashigo Сама
Челси — современная художница, которая решила создать свою следующую работу с использованием лестниц. Она хочет объединить несколько лестниц и нарисовать красивый узор.
Лестница может быть представлена как граф, называемый хасико. Всего существует n хасико, пронумерованных от 0 до n - 1. Хасико i длиной l_i имеет 2l_i + 6 вершин v_{i,0}, v_{i,1}, ..., v_{i,2li+5} и содержит ребра между парами вершин (v_{i,j}, v_{i,j+2}) (0 ≤ j ≤ 2l_i + 3) и (v_{i,2j}, v_{i,2j+1}) (1 ≤ j ≤ l_i + 1). На рисунке ниже показан пример хасико длиной 2, который соответствует графу из первого набора данных в примере ввода.
Два хасико i и j объединяются в позиции p (0 ≤ p ≤ l_i - 1) и q (0 ≤ q ≤ 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 ≤ n ≤ 30) и k (1 ≤ k ≤ 8).
Следующая строка содержит n целых чисел l_i (1 ≤ l_{i} ≤ 30), каждое из которых обозначает длину хасико i.
Следующие n - 1 строк содержат по четыре целых числа f_i (0 ≤ f_{i} ≤ n - 1), p_i (0 ≤ p_{i} ≤ l_{fi-1}), t_i (0 ≤ t_i ≤ n - 1), q_i (0 ≤ q_i ≤ l_{ti-1}). Это означает, что хасико f_i и хасико t_i объединяются в позиции p_i и позиции q_i. Вы можете предположить, что граф, полученный путем объединения n хасико, является связным, и степень каждой вершины графа не превышает 4.
Последний набор данных следует за строкой, содержащей два нуля.
Выходные данные
Для каждого набора данных выведите количество различных раскрасок по модулю 1000000007 в одной строке.