There are $n$ points arranged equidistantly on a circle. We connect every pair of points with a line segment. Please color each point with one of $1 \sim a$ colors and each line segment with one of $1 \sim b$ colors, such that the pattern remains different from the original after any rotation of the circle by an angle that is not a multiple of $2\pi$, or after any reflection across any straight line. Calculate the number of such colorings modulo $998244353$.

The value of $n$ is provided in a special way to ensure you can directly obtain its prime factorization.

Input

The first line contains a positive integer $k$, representing that $n$ can be written as the product of $k$ prime numbers.

The second line contains $k$ prime numbers $p_1, p_2, \dots, p_k$, where $n$ is their product.

The third line contains two positive integers $a$ and $b$, as defined in the problem.

Output

Output a single integer representing the number of colorings modulo $998244353$.

Examples

Input 1

1
3
2 2

Output 1

24

Subtasks

For $40\%$ of the data, $n=3 \sim 42$, with one test case for each value, each worth $1$ point.

For $75\%$ of the data, $n \le 10^{12}$.

For $100\%$ of the data, $p_i \le 10^9$, $3 \le n \le 10^{18}$, $1 \le a, b \le 10^8$.