题目描述

给你一棵 $n$ 个点带点权的树，第 $i$ 个点的点权为 $v_i$。

定义有向路径 $s\rightarrow e$ 的权值的计算方法为：

• 设从 $s$ 到 $e$ 的路径经过的点的点权分别为 $z_{0,1,\cdots,l}$，则该条路径的权值为 $(z_0k^0+z_1k^1+\cdots+z_lk^l)\bmod y$，记为 $t(s\rightarrow e)$。

另给定常数 $r$，定义函数 $f(x)=[x=r]$。现在让你求满足以下条件的三元组 $(p_1,p_2,p_3)$ 的个数：（三个点可以相同）

• $f(t(p_1\rightarrow p_2))=f(t(p_1\rightarrow p_3))=f(t(p_2\rightarrow p_2))$

输入格式

第一行四个整数 $n,y,k,r$。

接下来一行 个数代表每个点的点权。

接下来 $n-1$ 行每行两个数代表树上一条边。

输出格式

输出一行代表答案。

样例 #1

样例输入 #1

3 5 2 1
4 3 1
1 2
2 3

样例输出 #1

14

样例 #2

见下发样例

提示

对于 $10\%$ 的数据，$n\le10$ 。

对于 $25\%$ 的数据，$n\le100$ 。

对于 $40\%$ 的数据，$n\le10000$ 。

对于另外 $15\%$ 的数据，树退化为一条链。

对于另外 $15\%$ 的数据，$k=1$ 。

对于 $100\%$ 的数据，$1\le n\le10^5,2\le y\le10^9,1\le k< y,0\le r,v_i< y$ ，保证 $y$ 是质数。