하시고 사마

첼시는 현대 미술가다. 다음 작품은 사다리로 만들기로 했다. 사다리 몇 개를 이어 붙인 다음, 그 위에 무늬를 칠할 생각이다.

사다리 하나를 hashigo라고 부르는 그래프로 나타낸다. hashigo는 0번부터 $n-1$번까지 $n$개가 있다. 길이가 $l_i$인 hashigo $i$는 정점 $v_{i,0}, v_{i,1}, \dots, v_{i,2l_i+5}$ 총 $2l_i+6$개로 이루어지고, 간선은 다음 두 종류다.

• $0 \le j \le 2l_i+3$인 모든 $j$에 대해 $(v_{i,j}, v_{i,j+2})$
• $1 \le j \le l_i+1$인 모든 $j$에 대해 $(v_{i,2j}, v_{i,2j+1})$

짝수 번호 정점은 $v_{i,0}, v_{i,2}, \dots, v_{i,2l_i+4}$ 순서로 이어져 기둥 하나를 이루고, 홀수 번호 정점은 $v_{i,1}, v_{i,3}, \dots, v_{i,2l_i+5}$ 순서로 이어져 나머지 기둥 하나를 이룬다. 두 기둥은 가로대 $l_i+1$개로 이어지며, 양 끝의 $v_{i,0}$, $v_{i,1}$, $v_{i,2l_i+4}$, $v_{i,2l_i+5}$에는 가로대가 붙지 않는다.

hashigo $i$와 hashigo $j$를 위치 $p$ ($0 \le p \le l_i-1$), 위치 $q$ ($0 \le q \le l_j-1$)에서 붙이는 연산은 다음 네 쌍을 각각 한 정점으로 합치는 것이다.

$(v_{i,2p+2}, v_{j,2q+2}), \quad (v_{i,2p+3}, v_{j,2q+4}), \quad (v_{i,2p+4}, v_{j,2q+3}), \quad (v_{i,2p+5}, v_{j,2q+5})$

첼시는 이 연산을 $n-1$번 해서 hashigo $n$개를 하나로 잇는다. 연산을 모두 마친 그래프는 연결 그래프이고, 모든 정점의 차수가 4 이하다.

이제 각 정점을 검은색이나 흰색으로 칠하는데, 지켜야 할 조건이 하나 있다.

• 같은 색으로 칠한 정점끼리 이어져 생기는 연결 요소 중 가장 큰 것의 크기가 $k$ 이하다.

첼시는 가능한 무늬를 모두 살펴보고 가장 마음에 드는 것을 고르고 싶지만, 경우의 수가 아주 많다. 조건을 만족하는 칠하기가 몇 가지인지 세어라.

입력은 데이터 세트 여러 개로 이루어지고, 각 데이터 세트의 형식은 다음과 같다.

n k
l0 l1 ... ln-1
f0 p0 t0 q0
...
fn-2 pn-2 tn-2 qn-2

첫째 줄에 정수 $n$ ($1 \le n \le 30$)과 $k$ ($1 \le k \le 8$)가 주어진다.

둘째 줄에 hashigo $i$의 길이 $l_i$ ($1 \le l_i \le 30$)가 $n$개 주어진다.

이어지는 $n-1$개 줄에는 정수 네 개 $f_i$ ($0 \le f_i \le n-1$), $p_i$ ($0 \le p_i \le l_{f_i}-1$), $t_i$ ($0 \le t_i \le n-1$), $q_i$ ($0 \le q_i \le l_{t_i}-1$)가 주어진다. hashigo $f_i$와 hashigo $t_i$를 각각 위치 $p_i$와 위치 $q_i$에서 붙인다는 뜻이다. hashigo $n$개를 모두 붙여 만든 그래프는 연결 그래프이고 모든 정점의 차수가 4 이하라고 가정해도 된다.

마지막 데이터 세트 다음 줄에는 0 두 개가 주어진다.

데이터 세트마다 서로 다른 칠하기의 수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.