Tree Labeling

Consider a tree $T = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges. A vertex joined to $v$ by an edge is a neighbor of $v$ in $T$, and the set of all neighbors of $v$ is written $N(v)$.

A labeling of $T$ is a one-to-one and onto function $f : V \to \{1, 2, \dots, |V|\}$.

Two labelings $f$ and $g$ are equivalent when the following holds: for every vertex $u \in V$ there is a vertex $v \in V$ such that $f(u) = g(v)$ and $\{f(u') \mid u' \in N(u)\} = \{g(v') \mid v' \in N(v)\}$. By this definition, a labeling $f$ is equivalent to itself.

The figure below shows two equivalent labelings.

Given a tree $T$ and a labeling $f$ of $T$, write a program that counts the labelings equivalent to $f$. Since $f$ is equivalent to itself, include $f$ in the count.

Your program reads from standard input. The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains the number of vertices $N$ ($1 \le N \le 1000$) of the tree. Each of the next $N-1$ lines contains two integers $i$ and $j$ ($1 \le i, j \le N$), which describe an edge joining vertex $i$ and vertex $j$. The next line contains $N$ integers describing a labeling, where the $i$th number is the label of vertex $i$. All integers are separated by a single space.

Your program writes to standard output. For each test case, print the number of labelings equivalent to $f$ on one line. This number can grow very large, so print the exact value without taking a modulo.