Programming Geek
Rated 4.7/5 based on 1446 reviews

MockVita 2018 Problem: Finding Products

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

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.