434_E. Furukawa Nagisa's Tree_28639
One day, Okazaki Tomoya has bought a tree for Furukawa Nagisa's birthday. The tree is so strange that every node of the tree has a value. The value of the i-th node is vi. Now Furukawa Nagisa and Okazaki Tomoya want to play a game on the tree.

Let (s, e) be the path from node s to node e, we can write down the sequence of the values of nodes on path (s, e), and denote this sequence as S(s, e). We define the value of the sequence G(S(s, e)) as follows. Suppose that the sequence is z0, z1...zl - 1, where l is the length of the sequence. We define G(S(s, e)) = z0 × k0 + z1 × k1 + ... + zl - 1 × kl - 1. If the path (s, e) satisfies <image>, then the path (s, e) belongs to Furukawa Nagisa, otherwise it belongs to Okazaki Tomoya.

Calculating who has more paths is too easy, so they want to play something more difficult. Furukawa Nagisa thinks that if paths (p1, p2) and (p2, p3) belong to her, then path (p1, p3) belongs to her as well. Also, she thinks that if paths (p1, p2) and (p2, p3) belong to Okazaki Tomoya, then path (p1, p3) belongs to Okazaki Tomoya as well. But in fact, this conclusion isn't always right. So now Furukawa Nagisa wants to know how many triplets (p1, p2, p3) are correct for the conclusion, and this is your task.

Input

The first line contains four integers n, y, k and x (1 ≤ n ≤ 105; 2 ≤ y ≤ 109; 1 ≤ k < y; 0 ≤ x < y) — n being the number of nodes on the tree. It is guaranteed that y is a prime number.

The second line contains n integers, the i-th integer is vi (0 ≤ vi < y).

Then follow n - 1 lines, each line contains two integers, denoting an edge of the tree. The nodes of the tree are numbered from 1 to n.

Output

Output a single integer — the number of triplets that are correct for Furukawa Nagisa's conclusion.

Examples

Input

1 2 1 0
1


Output

1


Input

3 5 2 1
4 3 1
1 2
2 3


Output

14


Input

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


Output

341
#include <bits/stdc++.h>
using namespace std;
int power(int a, int n, int mod) {
  int res;
  if (n == 0) return 1;
  res = power(a, n / 2, mod);
  res = (int)((long long)res * (long long)res % mod);
  if (n % 2) res = (int)((long long)res * (long long)a % mod);
  return res;
}
int in, tot, root, size[110000], value[110000], n, yy, k, xx, id1, id2,
    ex[110000], mod, dist[110000];
int yes[110000], no[110000], rev[110000], inf = 1100000000;
long long one[2][110000], ans;
bool vis[110000], is_first;
struct pp {
  int id, v1, v2, deep, v3, now_v;
  long long msize;
  long long tsum[2];
  bool operator<(const pp &temp) const { return v3 < temp.v3; }
};
vector<pp> anc[110000];
pp lst[110000];
int cnt_list;
vector<int> adj[110000];
int lower_bound(int root, int left, int right, pp now) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (anc[root][mid] < now)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return left;
}
int upper_bound(int root, int left, int right, pp now) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (now < anc[root][mid])
      right = mid - 1;
    else
      left = mid + 1;
  }
  return right;
}
void dl_data(int root, int flag) {
  int i, j, s, p, q, siz, lo, hi, temp;
  long long sum, ptot = 0, same = 0, tnt = 0, tot_no = 0, tot = 0;
  pp now;
  if (root < 0) return;
  siz = anc[root].size();
  for (i = 0; i < siz; i++) {
    temp = ((xx - anc[root][i].v1) % mod + mod) % mod;
    temp = (int)((long long)temp * (long long)rev[anc[root][i].deep] % mod);
    anc[root][i].v3 = temp;
  }
  sort(anc[root].begin(), anc[root].end());
  sum = tot = 0;
  for (i = 0; i < siz; i++) {
    sum += one[0][anc[root][i].id];
    tot += one[1][anc[root][i].id];
    anc[root][i].tsum[0] = one[0][anc[root][i].id];
    anc[root][i].tsum[1] = one[1][anc[root][i].id];
    if (i > 0) {
      anc[root][i].tsum[0] += anc[root][i - 1].tsum[0];
      anc[root][i].tsum[1] += anc[root][i - 1].tsum[1];
    }
  }
  for (i = 0; i < siz; i++) {
    now.v3 = (anc[root][i].v2 - anc[root][i].now_v) % mod;
    if (now.v3 < 0) now.v3 += mod;
    lo = lower_bound(root, 0, siz - 1, now);
    hi = upper_bound(root, 0, siz - 1, now);
    long long ns = 0;
    tot_no += sum + tot;
    if (lo <= hi) {
      ns += anc[root][hi].tsum[0];
      if (lo > 0) ns -= anc[root][lo - 1].tsum[0];
      ns += anc[root][hi].tsum[1];
      if (lo > 0) ns -= anc[root][lo - 1].tsum[1];
      tot_no -= ns;
    }
  }
  ans += flag * (-tot_no + (long long)siz * (long long)sum);
}
void deal_data(int root, int flag, bool ff) {
  int temp, i, j, s, p, q, siz, lo, hi;
  pp now;
  if (root < 0) return;
  siz = anc[root].size();
  for (i = 0; i < siz; i++) {
    temp = ((xx - anc[root][i].v1) % mod + mod) % mod;
    temp = (int)((long long)temp * (long long)rev[anc[root][i].deep] % mod);
    anc[root][i].v3 = temp;
  }
  for (j = 0; j < 2; j++) {
    if (j == 1) {
      for (i = 0; i < siz; i++) {
        temp = (anc[root][i].v2 - anc[root][i].now_v) % mod;
        if (temp < 0) temp += mod;
        anc[root][i].v3 = temp;
        temp = (int)((long long)(xx - anc[root][i].v1) *
                     (long long)rev[anc[root][i].deep] % mod);
        if (temp < 0) temp += mod;
      }
    }
    sort(anc[root].begin(), anc[root].end());
    for (i = 0; i < siz; i++) {
      if (j == 0) {
        now.v3 = (anc[root][i].v2 - anc[root][i].now_v) % mod;
        if (now.v3 < 0) now.v3 += mod;
      } else {
        now.v3 = (int)((long long)(xx - anc[root][i].v1) *
                       (long long)rev[anc[root][i].deep] % mod);
        if (now.v3 < 0) now.v3 += mod;
      }
      lo = lower_bound(root, 0, siz - 1, now);
      hi = upper_bound(root, 0, siz - 1, now);
      int dnt = hi - lo + 1;
      one[j][anc[root][i].id] += flag * dnt;
    }
  }
}
void get_data(int root, int id1, int id2, int vv1, int vv2, int deep) {
  int id, i, j, s, p, q, siz = adj[id1].size(), nv1, nv2;
  pp now;
  now.id = id1;
  now.v1 = vv1;
  now.v2 = vv2;
  now.now_v = value[root];
  now.deep = deep;
  anc[root].push_back(now);
  for (i = 0; i < siz; i++) {
    id = adj[id1][i];
    if (id == id2 || vis[id]) continue;
    nv1 = (int)((long long)vv1 * (long long)k % mod);
    nv1 = (nv1 + value[id]) % mod;
    nv2 = (int)((long long)ex[deep + 1] * (long long)value[id] % mod);
    nv2 = (nv2 + vv2) % mod;
    get_data(root, id, id1, nv1, nv2, deep + 1);
  }
}
void get_size(int id1, int id2) {
  int rt, id, i, j, s, p, q, siz = adj[id1].size();
  size[id1] = 1;
  for (i = 0; i < siz; i++) {
    id = adj[id1][i];
    if (id == id2 || vis[id]) continue;
    get_size(id, id1);
    size[id1] += size[id];
  }
}
void choose_root(int id1, int id2) {
  int ax = tot - size[id1], id, i, j, s, p, q, siz = adj[id1].size();
  for (i = 0; i < siz; i++) {
    id = adj[id1][i];
    if (id == id2 || vis[id]) continue;
    choose_root(id, id1);
    ax = max(ax, size[id]);
  }
  if (in > ax) {
    in = ax;
    root = id1;
  }
}
void fir_dfs(int id1, int id2) {
  int id, i, j, s, p, q, siz = adj[id1].size();
  vector<pp> pt;
  vis[id1] = true;
  get_data(id1, id1, -1, value[id1], value[id1], 0);
  if (!is_first) {
    pt.clear();
    for (i = 0; i < anc[id1].size(); i++) {
      pt.push_back(anc[id1][i]);
      anc[id1][i] = lst[anc[id1][i].id];
    }
    deal_data(id1, -1, 0);
    for (i = 0; i < anc[id1].size(); i++) anc[id1][i] = pt[i];
  }
  deal_data(id1, 1, 0);
  is_first = false;
  for (i = 0; i < anc[id1].size(); i++) {
    id = anc[id1][i].id;
    lst[id] = anc[id1][i];
  }
  for (i = 0; i < siz; i++) {
    id = adj[id1][i];
    if (vis[id]) continue;
    get_size(id, -1);
    tot = size[id];
    in = inf;
    choose_root(id, -1);
    fir_dfs(root, -1);
  }
}
void sec_dfs(int id1, int id2) {
  int i, j, s, p, q, siz = adj[id1].size(), id;
  vector<pp> pt;
  vis[id1] = true;
  if (!is_first) {
    pt.clear();
    for (i = 0; i < anc[id1].size(); i++) {
      pt.push_back(anc[id1][i]);
      anc[id1][i] = lst[anc[id1][i].id];
    }
    dl_data(id1, -1);
    for (i = 0; i < anc[id1].size(); i++) anc[id1][i] = pt[i];
  }
  dl_data(id1, 1);
  for (i = 0; i < anc[id1].size(); i++) lst[anc[id1][i].id] = anc[id1][i];
  is_first = false;
  for (i = 0; i < siz; i++) {
    id = adj[id1][i];
    if (vis[id]) continue;
    get_size(id, -1);
    tot = size[id];
    in = inf;
    choose_root(id, -1);
    sec_dfs(root, -1);
  }
}
int main() {
  int i, j, s, p, q, id;
  scanf("%d%d%d%d", &n, &yy, &k, &xx);
  mod = yy;
  for (i = 0; i < n; i++) {
    scanf("%d", &value[i]);
    adj[i].clear();
  }
  ex[0] = 1;
  rev[0] = 1;
  for (i = 1; i <= n; i++) {
    ex[i] = (int)((long long)ex[i - 1] * (long long)k % mod);
    rev[i] = power(ex[i], mod - 2, mod);
  }
  for (i = 0; i < n - 1; i++) {
    scanf("%d%d", &id1, &id2);
    id1--;
    id2--;
    adj[id1].push_back(id2);
    adj[id2].push_back(id1);
  }
  for (i = 0; i < n; i++) anc[i].clear();
  memset(vis, false, sizeof(vis));
  get_size(0, -1);
  tot = size[0];
  in = inf;
  choose_root(0, -1);
  memset(one, 0, sizeof(one));
  for (i = 0; i < n; i++) lst[i].id = i;
  is_first = true;
  ans = 0;
  fir_dfs(root, -1);
  memset(vis, false, sizeof(vis));
  get_size(0, -1);
  tot = size[0];
  in = inf;
  choose_root(0, -1);
  ans = 0;
  is_first = true;
  sec_dfs(root, -1);
  for (i = 0; i < n; i++) ans += (n - one[0][i]) * (n - one[0][i]);
  printf("%I64d\n", ans);
  return 0;
}

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
 1 2 1 0
1
 3 5 2 1
4 3 1
1 2
2 3
 10 3 2 0
2 0 1 1 2 2 2 2 2 0
1 10
10 3
10 8
3 7
1 2
1 5
10 9
10 6
6 4
 10 815165809 4938204 366175867
30926 25854 8579 5159 336 29062 9475 15525 25633 21617
1 2
1 8
2 4
4 10
1 3
10 6
2 5
5 9
2 7
 9 5 4 2
0 1 0 3 1 4 2 2 4
1 5
5 8
5 9
5 4
5 7
4 2
1 6
5 3
 13 11 7 5
1 0 0 6 9 5 3 1 7 0 5 3 0
1 10
10 13
10 12
12 7
7 8
8 4
12 6
4 9
13 5
5 3
10 11
8 2
 8 5 1 1
0 3 4 3 0 3 2 0
1 5
1 7
7 3
5 4
3 2
1 6
6 8
 3 3 1 2
2 1 1
1 2
2 3
 16 17 3 14
3 10 6 3 8 8 7 16 0 9 1 4 3 1 6 11
1 6
1 4
1 11
6 5
5 14
5 3
1 8
1 2
6 15
4 16
1 12
2 9
12 13
5 7
15 10
 3 13 9 0
5 9 3
1 2
1 3
 4 13 5 9
11 9 2 11
1 2
2 3
2 4
 2 11 10 7
3 10
1 2
 6 19 5 16
18 0 12 5 0 9
1 2
1 5
2 6
6 3
6 4
 30 73121 39984 53821
19482 6851 15101 14876 20487 31835 30036 30719 12522 26197 31937 20457 9178 19895 30019 3245 25587 28287 8941 14815 1799 7562 1085 9435 2703 29110 26282 28425 11496 2116
1 21
1 26
26 30
26 15
15 17
1 27
27 9
27 22
15 18
18 16
22 29
18 25
30 24
15 2
29 8
18 11
21 19
17 23
21 12
1 20
26 6
11 5
26 10
30 14
16 7
23 13
11 4
25 3
27 28
 29 1277 344 649
187 1241 309 20 768 381 1043 804 588 263 795 172 203 849 779 58 110 337 291 894 601 77 943 528 21 167 457 126 957
1 29
29 28
1 21
28 5
29 8
1 10
1 2
28 17
5 18
29 27
27 15
8 12
8 11
1 7
27 23
10 19
29 24
1 3
18 20
24 22
10 4
17 25
1 16
4 9
9 13
24 6
22 14
22 26
 11 70327 50222 52541
8473 14143 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
4 11
1 6
4 5
5 2
6 8
4 3
8 10
5 7
5 9
 5 3 1 1
0 0 0 0 1
1 5
5 4
4 3
3 2
 5 2 1 1
1 0 0 0 0
1 2
1 5
5 3
1 4
 22 7 1 2
0 4 3 3 1 5 3 3 1 4 2 5 3 1 4 1 0 6 5 1 3 6
1 18
18 22
1 8
8 3
3 13
8 12
22 21
1 4
13 7
7 6
4 2
3 11
18 15
13 5
18 17
4 16
11 10
3 14
4 19
22 20
10 9
 5 41897 23399 13294
21304 8954 19233 2773 26606
1 4
4 3
4 2
2 5
 3 3 2 2
2 1 1
1 2
2 3
 3 13 9 0
5 9 3
2 2
1 3
 11 70327 50222 52541
8473 14143 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
4 11
1 6
4 5
5 2
6 8
4 3
8 10
4 7
5 9
 5 3 1 1
0 0 0 1 1
1 5
5 4
4 3
3 2
 5 41897 23399 13294
21304 8954 19233 2773 26606
1 4
4 3
4 2
1 5
 1 2 2 0
1
 5 3 1 1
1 0 0 1 1
1 5
5 4
4 3
3 2
 13 11 7 5
1 0 0 6 9 0 3 1 7 0 5 3 0
1 10
10 13
10 12
12 7
7 8
8 4
12 6
4 9
13 5
5 3
10 11
8 2
 8 5 1 1
0 3 4 3 0 3 1 0
1 5
1 7
7 3
5 4
3 2
1 6
6 8
 3 3 1 2
2 1 0
1 2
2 3
 3 13 9 0
5 7 3
1 2
1 3
 4 13 5 9
11 9 2 3
1 2
2 3
2 4
 2 11 10 7
0 10
1 2
 6 19 5 16
18 0 12 5 1 9
1 2
1 5
2 6
6 3
6 4
 29 1277 344 649
187 1241 309 20 768 381 721 804 588 263 795 172 203 849 779 58 110 337 291 894 601 77 943 528 21 167 457 126 957
1 29
29 28
1 21
28 5
29 8
1 10
1 2
28 17
5 18
29 27
27 15
8 12
8 11
1 7
27 23
10 19
29 24
1 3
18 20
24 22
10 4
17 25
1 16
4 9
9 13
24 6
22 14
22 26
 22 7 1 2
0 4 3 3 1 5 3 3 1 4 2 5 3 0 4 1 0 6 5 1 3 6
1 18
18 22
1 8
8 3
3 13
8 12
22 21
1 4
13 7
7 6
4 2
3 11
18 15
13 5
18 17
4 16
11 10
3 14
4 19
22 20
10 9
 8 13 8 12
0 1 7 4 12 0 8 12
1 8
8 4
4 6
6 2
2 3
8 5
2 7
 3 5 2 1
4 0 1
1 2
2 3
 3 3 2 2
2 0 1
1 2
2 3
 13 11 7 5
2 0 0 6 9 0 3 1 7 0 5 3 0
1 10
10 13
10 12
12 7
7 8
8 4
12 6
4 9
13 5
5 3
10 11
8 2
 2 11 10 0
0 10
1 2
 3 5 2 1
0 0 1
1 2
2 3
 3 13 9 0
5 5 3
2 2
1 3
 11 70327 50222 52541
12462 14143 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
4 11
1 6
4 5
5 2
6 8
4 3
8 10
4 7
5 9
 5 73259 23399 13294
21304 8954 19233 2773 26606
1 4
4 3
4 2
1 5
 11 70327 50222 52541
12462 14143 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
1 11
1 6
4 5
5 2
6 8
4 3
8 10
4 7
5 9
 5 3 1 1
1 0 0 1 1
1 5
5 4
4 3
1 2
 11 70327 79707 52541
8473 14143 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
4 11
1 6
4 5
5 2
6 8
4 3
8 10
5 7
5 9
 1 41897 23399 13294
21304 8954 19233 2773 26606
1 4
4 3
4 2
2 5
 5 41897 23399 13294
21304 8954 19233 2773 26606
1 4
2 3
4 2
1 5
 11 70327 50222 52541
12462 7445 6080 32594 6028 25465 32146 17052 21168 31052 25500
1 4
4 11
1 6
4 5
5 2
6 8
4 3
8 10
4 7
5 9
 5 3 1 0
1 0 0 1 1
1 5
5 4
4 3
1 2
 3 3 1 2
0 1 0
1 2
2 3
 29 1277 344 649
187 1241 309 20 768 381 721 804 588 263 795 172 203 849 779 6 110 337 291 894 601 77 943 528 21 167 457 126 957
1 29
29 28
1 21
28 5
29 8
1 10
1 2
28 17
5 18
29 27
27 15
8 12
8 11
1 7
27 23
10 19
29 24
1 3
18 20
24 22
10 4
17 25
1 16
4 9
9 13
24 6
22 14
22 26
 1 41897 23399 13294
21304 8954 19233 2773 26606
2 4
4 3
4 2
2 5
 3 3 4 2
2 0 1
1 2
2 3

341
 1
 14
 454
 1000
 436
 1689
 326
 9
 3610
 27
 55
 4
 216
 27000
 24389
 1331
 59
 65
 6757
 125
 14 27 1331 53 125 1 59 1692 263 21 20 48 8 216 24389 6367 429 17 11 1794 5 15 27 1331 125 1331 53 1331 1 125 1331 53 27 24389 1 15