На окружности равноудаленно расположены $n$ точек. Мы соединяем любые две точки отрезком. Вам необходимо раскрасить каждую точку в один из $a$ цветов, а каждый отрезок — в один из $b$ цветов так, чтобы при любом повороте окружности на угол, не кратный $2\pi$, или при любом отражении относительно прямой, итоговый узор не совпадал с исходным. Вычислите количество таких способов по модулю $998244353$.

Значение $n$ в этой задаче дается в особом виде, чтобы вы могли напрямую получить его разложение на простые множители.

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

Первая строка содержит целое положительное число $k$, означающее, что $n$ можно представить как произведение $k$ простых чисел.

Вторая строка содержит $k$ простых чисел $p_1, p_2, \dots, p_k$, произведение которых равно $n$.

Третья строка содержит два целых положительных числа $a$ и $b$, имеющих смысл, описанный в условии.

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

Выведите одно целое число — количество способов по модулю $998244353$.

Примеры

Пример 1

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

1
3
2 2

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

24

Подзадачи

Для $40\%$ данных: $n$ принимает значения от $3$ до $42$ (по одному тесту на каждое значение, каждый тест оценивается в $1$ балл).

Для $75\%$ данных: $n \le 10^{12}$.

Для $100\%$ данных: $p_i \le 10^9$, $3 \le n \le 10^{18}$, $1 \le a, b \le 10^8$.