题目描述
给你一棵 $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$ 是质数。