G. Подходящая команда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Близится следующий сезон, поэтому Вы решили собрать команду из двух или трех человек. У Вас есть $$$n$$$ кандидатов, $$$i$$$-й кандидат имеет ранг $$$a_i$$$. Но у Вас есть какие-то странные ограничения: если Ваш ранг $$$v$$$ и Вы выбрали кандидатов $$$i$$$ и $$$j$$$, то должно выполняться условие $$$GCD(v, a_i) = X$$$ и $$$LCM(v, a_j) = Y$$$.

Вы очень опытный участник, поэтому Вы можете сделать свой ранг любым неотрицательным целым числом, однако $$$X$$$ и $$$Y$$$ связаны с Вашим днем рождения, поэтому они фиксированы.

И вот Вы хотите узнать количество пар $$$(i, j)$$$ таких, что существует $$$v$$$, что $$$GCD(v, a_i) = X$$$ и $$$LCM(v, a_j) = Y$$$. Разрешена ситуация $$$i = j$$$, просто ваша команда будет состоять из двух участников.

$$$GCD$$$ — это наибольший общий делитель двух чисел, а $$$LCM$$$ — наименьшее общее кратное.

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

Первая строка содержит три целых числа $$$n$$$, $$$X$$$ и $$$Y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le X \le Y \le 10^{18}$$$) — количество кандидатов и соответствующие константы.

Вторая строка содержит $$$n$$$ целых чисел через пробел: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — ранги кандидатов.

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

Выведите единственное число — количество пар $$$(i, j)$$$, что существует $$$v$$$ такой, что $$$GCD(v, a_i) = X$$$ и $$$LCM(v, a_j) = Y$$$. Ситуация $$$i = j$$$ разрешена.

Примеры
Входные данные
12 2 2
1 2 3 4 5 6 7 8 9 10 11 12
Выходные данные
12
Входные данные
12 1 6
1 3 5 7 9 11 12 10 8 6 4 2
Выходные данные
30
Примечание

В первом примере следующие пары валидны: $$$a_j = 1$$$ и $$$a_i = [2, 4, 6, 8, 10, 12]$$$, либо $$$a_j = 2$$$ и $$$a_i = [2, 4, 6, 8, 10, 12]$$$. Ранг $$$v$$$ в обоих случаях может быть равен $$$2$$$.

Во втором тесте следующие пары валидны:

  • $$$a_j = 1$$$ и $$$a_i = [1, 5, 7, 11]$$$;
  • $$$a_j = 2$$$ и $$$a_i = [1, 5, 7, 11, 10, 8, 4, 2]$$$;
  • $$$a_j = 3$$$ и $$$a_i = [1, 3, 5, 7, 9, 11]$$$;
  • $$$a_j = 6$$$ и $$$a_i = [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2]$$$.