J. GCD and LCM Subsequences
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$N$$$.

Each element satisfies $$$1 \le A_i \le 10^{12}$$$.

You are also given two integers $$$G$$$ and $$$L$$$.

Your task is to count the number of non-empty subsequences of $$$A$$$ such that:

  • The greatest common divisor (GCD) of all elements in the subsequence is exactly $$$G$$$.
  • The least common multiple (LCM) of all elements in the subsequence is exactly $$$L$$$.

Since the answer may be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$).

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^{12}$$$).

The third line contains two integers $$$G$$$ and $$$L$$$ ($$$1 \le G, L \le 10^{12}$$$).

Output

Print a single integer — the number of valid subsequences modulo $$$998244353$$$.

Examples
Input
5
50 4 50 4 100
2 100
Output
18
Input
5
8 2 2 1 2
1 8
Output
8
Note

A subsequence of an array is obtained by deleting zero or more elements without changing the relative order of the remaining elements. The subsequence must be non-empty.

The GCD of a sequence is the greatest common divisor of all its elements. The LCM of a sequence is the least common multiple of all its elements.

It is not guaranteed that $$$G$$$ divides $$$L$$$. If no valid subsequence exists, print $$$0$$$.