## Finding Product

### Problem Description:

### 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

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.

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.

## No comments :

## Post a Comment