Limits 2s, 512 MB

Mr Makor has a set S of n integers. He calls a sequence of length k special if every element of the sequence is taken from the set S (the sequence can have the same element multiple numbers of times) and the summation of every two consecutive elements is divisible by m. More formally, if A is a sequence of length k and Ai is the ith element of the sequence then sequence A will be special if Ai ϵ S for every 1 ≤ i ≤ k and m | (Ai + Ai+1) (means m divides Ai + Ai+1) for every 1 ≤ i < k. Mr Makor was thinking about giving some sequences to his friends as a gift. So he thought about the number of distinct special sequences he can make. As this number may be quite large, you need to find its remainder modulo (109+7).

Note: Two sequences will be different if there exists an index where two sequences have two different values at that index.

Input

The first line will contain an integer n(1 ≤ n ≤ 106). Next line will contain n distinct integers Si(1 ≤ Si ≤ 109) where Si is the ith element of the set.

The last line will contain two integers k and m (1 ≤ k, m ≤ 109).

Output

Output the number of unique special sequences Mr Makor can make modulo (109+7).

Sample

InputOutput
2
6 4
2 10
2

Submit

Login to submit.

Statistics

91% Solution Ratio
mohanr7073Earliest, Dec '19
nusuBotFastest, 0.4s
riyad000Lightest, 52 MB
kzvd4729Shortest, 672B
Toph uses cookies. By continuing you agree to our Cookie Policy.