Clock Tree

Farmer John's new barn has a truly strange design: it consists of $n$ rooms, conveniently numbered $\mathrm{1...}n$, and $n-1$ corridors. Each corridor connects a pair of rooms, in such a way that it is possible to walk from any room to any other room along a series of corridors.

Every room in the barn has a circular clock on the wall with the standard integers $\mathrm{1...12}$ around its face. However, these clocks only have one hand, which always points directly at one of the integers on the clock face (it never points between two of these integers).

Bessie the cow wants to synchronize all the clocks in the barn so they all point to the integer $12$. However, she is somewhat simple-minded, and as she walks around the barn, every time she enters a room, she moves the hand on its clock ahead by one position. For example, if the clock pointed at $5$, it would now point at $6$, and if the clock pointed at $12$, it would now point at $1$. If Bessie enters the same room multiple times, she advances the clock in that room every time she enters.

Please determine the number of rooms in which Bessie could start walking around the barn such that she could conceivably set all the clocks to point to **12**. Note that Bessie does not initially advance the clock in her starting room, but she would advance the clock in that room any time she re-entered it. Clocks do not advance on their own; a clock only advances if Bessie enters its room. Furthermore, once Bessie enters a corridor she must exit through the other end (it is not allowed to walk partially through the corridor and loop back around to the same room).

Input

The first line contains $n(2\le n\le 2500)$. The next line contains $n$ integers, each in the range $\mathrm{1...12}$, specifying the initial clock setting in each room. The next $n-1$ lines each describe a corridor in terms of two integers $a$ and $b$, each in the range $\mathrm{1...}n$, giving the room numbers connected by the corridor.

Output

Print the number of rooms in which Bessie could start, such that it is possible for her to set all clocks to point to $12$.

Examples

In this example, Bessie can set all the clocks to point to $12$ if and only if she starts in room $2$ (for example, by moving to room $1,2,3,2$ and finally $4$).