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.
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 the number of unique special sequences Mr Makor can make modulo (109+7).
2 6 4 2 10