E. Дерево Фурукава Нагисы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Однажды Оказаки Томоя купил дерево на день рождения Фурукава Нагисы. Дерево было немного странное, у каждой вершины дерева было написано значение. Обозначим значение у 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) удовлетворяет , тогда путь (s, e) принадлежит Фурукава Нагисе, в противном случае он принадлежит Оказаки Томоя.

Считать, у кого больше путей, слишком легко, поэтому ребята хотят поиграть во что-то посложнее. Фурукава Нагиса выдвинула гипотезу:

  • если пути (p1, p2) и (p2, p3) принадлежат ей, то и путь (p1, p3) тоже принадлежит ей;
  • если пути (p1, p2) и (p2, p3) принадлежат Оказаки Томоя, то и путь (p1, p3) тоже принадлежит Оказаки Томоя.

Конечно, описанное выполняется не для всех троек (p1, p2, p3). Итак, теперь Фурукава Нагиса хочет узнать, сколько троек (p1, p2, p3) удовлетворяют ее условию — и это ваша задача.

Входные данные

В первой строке записано четыре целых числа n, y, k и x (1 ≤ n ≤ 105; 2 ≤ y ≤ 109; 1 ≤ k < y; 0 ≤ x < y), здесь n является количеством вершин дерева. Гарантируется, что y является простым числом.

Во второй строке записано n целых чисел: v1, v2, ..., vn (0 ≤ vi < y).

Затем следуют n - 1 строк, в каждой строке записано по два целых числа, обозначающих ребро дерева. Вершины дерева пронумерованы от 1 до n.

Выходные данные

Выведите единственное целое число — количество троек, удовлетворяющих гипотезе Фурукава Нагисы.

Примеры
Входные данные
1 2 1 0
1
Выходные данные
1
Входные данные
3 5 2 1
4 3 1
1 2
2 3
Выходные данные
14
Входные данные
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
Выходные данные
341