Хашіго Сама#4299

Хашіго Сама

20 секунд

256 мегабайтів

Дуже складна

Челсі — сучасна художниця, яка вирішила створити свою наступну роботу, використовуючи драбини. Вона планує поєднати кілька драбин, щоб намалювати красивий візерунок.

Драбину можна уявити як граф, відомий як хасіго. Існує $n$ хасіго, пронумерованих від $0$ до $n - 1$ n - 1. Хасіго $i$ з довжиною $l_{i}$ l_i має $2 l_{i} + 6$ 2l_i + 6 вершин $v_{i, 0}$ v_{i,0}, $v_{i, 1}$ v_{i,1}, ..., $v_{i, 2 l_{i} + 5}$ v_{i,2l_i+5} і містить ребра між парами вершин $(v_{i, j}, v_{i, j + 2})$ (v_{i,j}, v_{i,j+2}) $(0 \leq j \leq 2 l_{i} + 3)$ (0 \le j \le 2l_i + 3) та $(v_{i, 2 j}, v_{i, 2 j + 1})$ (v_{i,2j}, v_{i,2j+1}) $(1 \leq j \leq l_{i} + 1)$ (1 \le j \le l_i + 1). Нижче наведено приклад хасіго з довжиною $2$ , що відповідає графу з першого прикладу вхідних даних.

Дві хасіго $i$ та $j$ поєднуються на позиціях $p$ $(0 \leq p \leq l_{i} - 1)$ (0 \le p \le l_i - 1) та $q$ $(0 \leq q \leq l_{j} - 1)$ (0 \le q \le l_j - 1) шляхом злиття кожної пари вершин $(v_{i, 2 p + 2}, v_{j, 2 q + 2})$ (v_{i,2p+2}, v_{j,2q+2}), $(v_{i, 2 p + 3}, v_{j, 2 q + 4})$ (v_{i,2p+3}, v_{j,2q+4}), $(v_{i, 2 p + 4}, v_{j, 2 q + 3})$ (v_{i,2p+4}, v_{j,2q+3}) та $(v_{i, 2 p + 5}, v_{j, 2 q + 5})$ (v_{i,2p+5}, v_{j,2q+5}).

Челсі виконує цю операцію $n - 1$ n - 1 раз, щоб об'єднати $n$ хасіго. Після цього граф має бути зв'язним, а максимальний ступінь графа не повинен перевищувати $4$ . Нижче наведено приклад графа, отриманого шляхом поєднання трьох хасіго, що відповідає графу з другого прикладу вхідних даних.

Тепер вона вирішила розфарбувати кожну вершину в чорний або білий колір, дотримуючись наступної умови:

Максимальна кількість компонентів, утворених з'єднаними вершинами одного кольору, не повинна перевищувати $k$ .

Вона хоче спробувати всі можливі візерунки та вибрати найкращий. Однак кількість способів розфарбування може бути дуже великою. Оскільки вона не сильна в математиці чи обчисленнях, вона не може підрахувати кількість. Тож, будь ласка, допоможіть їй своїми чудовими навичками програмування!

Вхідні дані

Вхід містить кілька наборів даних, і кожен набір даних має наступний формат.

$n$ $k$

$l_{0}$ l_0 $l_{1}$ l_1 ... $l_{n - 1}$ l_{n-1}

$f_{0}$ f_0 $p_{0}$ p_0 $t_{0}$ t_0 $q_{0}$ q_0

...

$f_{n - 2}$ f_{n-2} $p_{n - 2}$ p_{n-2} $t_{n - 2}$ t_{n-2} $q_{n - 2}$ q_{n-2}

Перший рядок містить два цілі числа $n$ ( $1 \leq n \leq 30$ 1 \le n \le 30) і $k$ ( $1 \leq k \leq 8$ 1 \le k \le 8).

Наступний рядок містить $n$ цілих чисел $l_{i}$ l_i ( $1 \leq l_{i} \leq 30$ 1 \le l_i \le 30), кожне з яких позначає довжину хасіго $i$ .

Наступні $n - 1$ n - 1 рядків кожен містять чотири цілі числа $f_{i}$ f_i ( $0 \leq f_{i} \leq n - 1$ 0 \le f_i \le n - 1), $p_{i}$ p_i ( $0 \leq p_{i} \leq l_{f_{i}} - 1$ 0 \le p_i \le l_{f_i} - 1), $t_{i}$ t_i ( $0 \leq t_{i} \leq n - 1$ 0 \le t_i \le n - 1), $q_{i}$ q_i ( $0 \leq q_{i} \leq l_{t_{i}} - 1$ 0 \le q_i \le l_{t_i} - 1). Це означає, що хасіго $f_{i}$ f_i та хасіго $t_{i}$ t_i поєднуються на позиціях $p_{i}$ p_i та $q_{i}$ q_i. Ви можете припустити, що граф, отриманий шляхом поєднання $n$ хасіго, є зв'язним, а ступінь кожної вершини графа не перевищує $4$ .

Останній набір даних супроводжується рядком, що містить два нулі.

Вихідні дані

Для кожного набору даних виведіть кількість різних розфарбувань за модулем $1000000007$ у рядку.

Приклади

Приклад 1