It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
One day the tree manager wants to walk on a tree. The tree has N nodes numbered from 1 to N. This is a magical tree with a power w_i attached to the node i. When you walk from node u to v via a path (x₀,x₁,x₂,…,x_l ) where x₀=u and x_l=v, you gain a power of (l≥0). The tree manager has a magical prime number P, and he will only be happy when he gains a power that mod P equals zero.
Now the tree manager wants you to help him determine how many triples (u,v,t) that satisfy one of two conditions below:
1) He is always happy when walking from u to t, from t to v and from u to v.
2) He is always unhappy when walking from u to t, from t to v and from u to v

The first line contains three integers N, K and P(1≤N≤105,1≤K<P<109), as mentioned above.
The second line contains N integers w1,w2,…,wN (1≤wi≤109) as mentioned above.
In the next N-1 lines, each contains two integersui and vi (1≤ui,vi≤N,ui≠vi), denoting an edge between ui and vi.
It is guaranteed that those edges form a tree.

Print an single number denoting the answer in a single line.

3 2 11 
2 6 2
1 2
2 3

15

The 15
triples in the example are:
(1,1,1)
(1,1,2)
(1,2,1)
(1,2,2)
(2,1,1)
(2,1,2)
(2,2,1)
(2,2,2)
(2,2,3)
(2,3,2)
(2,3,3)
(3,2,2)
(3,2,3)
(3,3,2)
(3,3,3)