Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mr Makor And His Friends

By ovis96 · 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


Discussion
Statistics

93% Solution Ratio

mohanr7073Earliest, 1M ago

kzvd4729Fastest, 0.7s

EgorKulikovLightest, 55 MB

kzvd4729Shortest, 672B

Submit

Login to submit