有一天,冈崎朋也买了一棵树作为古川渚的生日礼物。这棵树很奇怪,树的每个节点都有一个值。第 i 个节点的值为 vi。现在古川渚和冈崎智也想在树上玩游戏。
设(s, e)为从节点s到节点e的路径,我们可以写出路径(s, e)上节点值的序列,并将该序列表示为S(s, e)。我们将序列 G(S(s, e)) 的值定义如下。假设序列为 z0, z1...zl - 1,其中 l 是序列的长度。我们定义 G(S(s, e)) = z0 × k0 + z1 × k1 + ... + zl - 1 × kl - 1。如果路径 (s, e) 满足 $$G(S(s,e)) \equiv x (\bmod y)$$,则路径 (s, e) 属于古川渚,否则属于冈崎智也。
计算谁拥有更多的路径太容易了,所以他们想要玩一些更困难的东西。古川渚认为,如果路径(p1,p2)和(p2,p3)属于她,那么路径(p1,p3)也属于她。另外,她认为如果路径(p1,p2)和(p2,p3)属于冈崎智也,那么路径(p1,p3)也属于冈崎智也。但事实上,这个结论并不总是正确的。现在古川渚想知道有多少个三元组 (p1, p2, p3) 的结论是正确的,这就是你的任务。
输入
第一行包含四个整数 n、y、k 和 x(1 ≤ n ≤ 105;2 ≤ y ≤ 109;1 ≤ k < y;0 ≤ x < y) - n 是树上的节点数。保证y是素数。
第二行包含 n 个整数,第 i 个整数是 vi (0 ≤ vi < y)。
然后是n - 1行,每行包含两个整数,表示树的一条边。树的节点编号为 1 到 n。
输出
输出一个整数——古川渚的结论正确的三元组的数量。
示例
输入 #1
1 2 1 0 1
输出 #1
1
输入 #2
3 5 2 1 4 3 1 1 2 2 3
输出 #2
14
输入 #3
8 13 8 12 0 12 7 4 12 0 8 12 1 8 8 4 4 6 6 2 2 3 8 5 2 7
输出 #3
341