Coloring a Tree with Merge Constraints

You are given a tree with n nodes (numbered 1 through n, with 1 ≤ n ≤ 10⁵) and k colors (2 ≤ k ≤ 5). The tree is rooted at node 1. In addition, you are given a color merge function \(\otimes\) defined for colors from 1 to k such that for any 1 ≤ a, b ≤ k, \(1 \le a \otimes b \le k\).

A coloring of the tree is an assignment of a color to every node. A coloring is valid if for every pair of nodes \(u, v\) that do not have an ancestor–descendant relationship (i.e. neither is an ancestor of the other), the color of their lowest common ancestor (LCA) is equal to the merge of the colors of \(u\) and \(v\); that is, if \(\text{LCA}(u,v)=w\) then it must hold that:

[ \text{color}(w) = \text{color}(u) \otimes \text{color}(v). ]

You are to count the number of valid colorings modulo \(10^9+7\). Note that the merge function is given as a k × k table. For example, if k=2, a possible merge table might be:

[ \begin{array}{c|cc} \otimes & 1 & 2 \ \hline 1 & 1 & 1 \ 2 & 1 & 2 \end{array} ]

In this example, for any two nodes \(u\) and \(v\) (which lie in different branches of some node \(w\)), if \(\text{color}(u)=2\) and \(\text{color}(v)=2\) then since \(2 \otimes 2=2\) the LCA must have color 2; otherwise, if one of them is colored 1 then the LCA must be 1.

Input/Output Requirements: See the sections below.

inputFormat

The first line contains two integers n and k: the number of nodes and the number of colors.

The next n − 1 lines each contain two integers u and v representing an edge in the tree.

The following k lines each contain k integers. The j-th integer in the i-th of these lines is the value of \(i \otimes j\) (1-indexed).

The tree is rooted at node 1.

outputFormat

Output a single integer – the number of valid colorings modulo \(10^9+7\).

sample

3 2
1 2
1 3
1 1
1 2

4