Хашіго Сама
Челсі — сучасна художниця, яка вирішила створити свою наступну роботу, використовуючи драбини. Вона планує поєднати кілька драбин, щоб намалювати красивий візерунок.
Драбину можна уявити як граф, відомий як хасіго. Існує 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 у рядку.