PLEASE ANSWER THIS QUESTION

Question

You are given a set of N positive integers and two small prime numbers P and Q (not necessarily distinct). You need to write a program to count the number of subsets of the set of N numbers whose product is divisible by PQ (the product of P and Q). Since the number K of such sets can be huge, output K modulo 1009 (the remainder when K is divided by 1009).

Constraints
N <= 300

P,Q <=50

The integers are <= 10000

Input Format
First line three comma separated integers N, P,Q

The next line contains N comma separated integers

Output
One integer giving the number of subsets the product of whose elements is divisible by PQ. Give the result modulo 1009.

Test Case
TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

Explanation
Example 1

Input

4,5,7

5,49,10,27

Output

6

Explanation

N is 4, P is 5, Q is 7. We need to find subsets of the numbers given so that the product of the elements is divisible by 35 (the product of 5 and 7). These subsets are (5,49),(5,49,10),(5,49,27),(5,49,10,27), (49,10),(49,10,27). There are 6 subsets, and the output is 6.

Example 2

Input

4,11,13

3,7,12,13

Output

0

Explanation

N is 4, P is 11, Q is 13. We need to find subsets of the numbers given so that the product of the elements is divisible by 143 (the product of 11 and 13).As none of the N numbers is divisible by 11 (a prime number), there are no subsets for which the product of the elements is divisible by 143. Hence the output is 0.

Answer 1

I don't get it.

Answer 2

I understand what you want, but why?