Cat-First Search

Taehee woke up one day on vertex 1 of a tree. Besides Taehee, there may be some cats on this tree.

On this tree, the following two events happen in order, once each, every second.

• Every cat either stays in place or moves once to an adjacent vertex. Each cat moves independently.
• Taehee moves once to one of the adjacent vertices. Taehee cannot stay in place.

After studying the structure of the graph, Taehee came up with the following search strategy. At the start, Taehee stands on vertex 1, holding a notebook with 1 written in it and a pen.

1. Let V be the set of vertices adjacent to the current vertex that are not yet recorded in the notebook.
   • If V is empty, go back to the adjacent vertex that has been in the notebook for the longest time.
   • If some vertex in V has a cat, go to the smallest-numbered such vertex.
   • Otherwise, go to the smallest-numbered vertex in V.
2. If the number of the arrived vertex is not in the notebook, write it down.
3. Repeat (1) and (2) until N integers are written in the notebook. Each repetition of (1) and (2) takes 1 second.

During the search, cats may end up on the same vertex as each other, or on the same vertex as Taehee.

After the search finishes, Taehee looks at the N integers in the notebook. At that moment an alarm rings, and Taehee wakes up.

Taehee remembers the N integers from the dream and remembers the structure of the tree exactly.

Taehee wants to know the minimum number of cats that makes this search possible, and where each cat started. For Taehee, count the number of possible starting point sets when the number of cats is the minimum.

A starting point set is an array whose length equals the number of cats, listing the vertex where each cat stands in non-decreasing order. Two arrays count as different if at least one element differs.

The first line contains the number of vertices N. ($2 \le N \le 10^5$)

Each of the next N-1 lines contains two integers U and V, meaning there is an edge between U and V in the tree. ($1 \le U, V \le N$, $U \ne V$)

The given graph is guaranteed to be a valid connected tree.

The last line contains N integers separated by spaces. These are the numbers Taehee wrote in the notebook, in order. The first value is always 1. Each integer from 1 to N appears exactly once, and this sequence is guaranteed to be a possible search order when the cats help as much as they can.

Print the number of distinct possible starting point sets for the cats when the number of cats is minimal, modulo $10^9+7$.