Micro bought a new ball having an initial color K. He is also having N boxes of color, where i^th box contains color A[i]. He wants to paint his new ball. So he selects some boxes out of the N boxes and paint the ball with the color in those boxes. If current color of ball is X and he paints it with a color Y the new color of the ball will be (X*Y)%M. The order in which he applies color on the ball does not matter. It is also possible that Micro does not choose any box in which case color of the ball does not change. Now Micro is interested in the expected value of the color on the ball. Expected value can be represented as $a rational number \frac{\textstyle P}{\textstyle Q}$ . If Q is not divisible by 10^9+7 there is a unique integer x (0 ≤ x < 10^9+7) where $P \equiv$ Qx % (10^9+7). He wants to know value of this integer x.

Input:
First line consists of an integer T denoting the number of test cases.
Second line consists of three space separated integers denoting N, K, and M.
Third line consists of N space separated integers denoting colors in the boxes.

Output:
Print the answer for each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N, M ≤ 1000
1 ≤ K, A[i] ≤ 10^9

SAMPLE INPUT
1
2 1 10
1 2

SAMPLE OUTPUT
500000005

Explanation

Here Micro has 4 options to choose from:
i) Choose none : Color of ball will not change i.e. will remain 1
ii) Choose 1^st box: Color of ball will become (1 * 1)%10=1
iii) Choose 2^nd box: Color of ball will become (1 * 2)%10=2
iv) Choose both boxes: Color of ball will become (((1 * 1)%10) * 2)%10 = 2

So expected value $= \frac{\textstyle (2 * 1 + 2 * 2) }{\textstyle 4} = \frac{\textstyle 6}{\textstyle 4}$
And finally we have 6 = (4 * 500000005)%(10^9+7). So x=500000005

见题面

见题面