Hashigo Sama

Chelsea is a modern artist. She decided to build her next work out of ladders. She joins several ladders together and then paints a pattern on the result.

One ladder is described by a graph called a hashigo. There are $n$ hashigos, numbered 0 through $n-1$. Hashigo $i$ has length $l_i$ and consists of the $2l_i+6$ vertices $v_{i,0}, v_{i,1}, \dots, v_{i,2l_i+5}$. Its edges come in two kinds.

• $(v_{i,j}, v_{i,j+2})$ for every $j$ with $0 \le j \le 2l_i+3$
• $(v_{i,2j}, v_{i,2j+1})$ for every $j$ with $1 \le j \le l_i+1$

The even numbered vertices are linked in the order $v_{i,0}, v_{i,2}, \dots, v_{i,2l_i+4}$ and form one rail, and the odd numbered vertices are linked in the order $v_{i,1}, v_{i,3}, \dots, v_{i,2l_i+5}$ and form the other rail. The two rails are connected by $l_i+1$ rungs, and the four end vertices $v_{i,0}$, $v_{i,1}$, $v_{i,2l_i+4}$, $v_{i,2l_i+5}$ carry no rung.

Hashigo $i$ and hashigo $j$ are combined at position $p$ ($0 \le p \le l_i-1$) and position $q$ ($0 \le q \le l_j-1$) by merging each of the following four pairs into a single vertex.

$(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})$

Chelsea performs this operation $n-1$ times to combine all $n$ hashigos. After the operations the graph is connected and no vertex has degree greater than 4.

She now paints every vertex black or white, subject to one condition.

• Every connected component formed by adjacent vertices of the same color has size at most $k$.

She would like to inspect every pattern and pick the best one, but the number of patterns is very large. Count the colorings that satisfy the condition.

The input contains several datasets. Each dataset has the following format.

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

The first line contains two integers $n$ ($1 \le n \le 30$) and $k$ ($1 \le k \le 8$).

The next line contains $n$ integers $l_i$ ($1 \le l_i \le 30$), the length of hashigo $i$.

Each of the following $n-1$ lines contains four integers $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$). It means that hashigo $f_i$ and hashigo $t_i$ are combined at position $p_i$ and position $q_i$. You may assume that the graph obtained by combining the $n$ hashigos is connected and that no vertex of the graph has degree greater than 4.

The last dataset is followed by a line containing two zeros.

For each dataset, print the number of different colorings modulo 1,000,000,007 on one line.