Yamca and Yamochka are huge fans of cooperative board games. They are capable of playing them day and night, but there are moments when it gets a bit boring. For example, right now Yamca and Yamochka have gathered together to explore a dungeon; however, at the entrance to the dungeon, they found a puzzle that needs to be solved to proceed further. Yamca, as a big fan and experienced lover of puzzles, immediately started solving it using his innovative method of finding a solution to any problem, called the shotgun approach!

Unfortunately, solving puzzles is not a fast process, and Yamochka finds it of little interest, so, to keep herself somewhat occupied, she decided to think more carefully about the dungeon exploration plan, namely, to choose the best order for clearing the rooms. The dungeon consists of N rooms, some pairs of which are connected by tunnels through which one can freely move between the rooms, in both directions. Also, from any room, any other room is reachable via the tunnels, and there are exactly N−1 tunnels in the dungeon in total. More formally, the dungeon is an undirected tree. The dungeon clearing happens as follows: first, Yamca and Yamochka teleport to any room of their choice and clear it, after which they act according to the following algorithm until all rooms are cleared:

A couple of hours ago, when the heroes were packing for the dungeon trip, they found a sequence of integers p of length N. Having found no use for it earlier, Yamochka decided to use it now; specifically, she decided that they would clear the rooms in such an order that the sequence in which the rooms were cleared would not be lexicographically greater than the sequence p. A sequence a is lexicographically greater than a sequence b if there exists an index i (1 ≤ i ≤ N) such that for any j (1 ≤ j < i) a_j=b_j and a_i>b_i. Now Yamochka is interested in how many distinct suitable sequences of room clearing exist.

The first line contains an integer N (1 ≤ N ≤ 10⁵).

The following N − 1 lines contain two integers x_i, y_i each — a pair of rooms between which there is a tunnel. It is guaranteed that the tunnels and rooms of the dungeon form a tree.

The last line contains a sequence of integers p of length N (1 ≤ p_i ≤ N).

Count the number of distinct suitable sequences of room clearing. Since this number can be quite large, output its remainder modulo 952426967.