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_0,x_1,x_2,…,x_l)$ where $x_0=u$ and $x_l=v$, you gain a power of $\sum_{i=0}^l w_{x_i}×K^i\ (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, P\ (1≤N≤10^5,\ 1≤K<P<10^9)$, as mentioned above.

The second line contains $N$ integers $w_1,w_2,…,w_N\ (1≤w_i≤10^9)$ as mentioned above.
In the next $N-1$ lines, each contains two integers $u_i, v_i\ (1≤u_i,v_i≤N,\ u_i≠v_i)$, denoting an edge between $u_i$ and $v_i$.
It is guaranteed that those edges form a tree.

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

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)