Company: MediaNet_8oct
Difficulty: medium
Omega Prime Subsets Problem Description Carl is bored of playing with ordinary prime numbers. Thus, he comes up with some special numbers called Omega Primes. A number X is called Omega Prime, if there exists no perfect square Y (Y > 1) such that Y divides X. For example, 6 is an Omega Prime because there is no perfect square except 1 that divides 6. On the other hand, 12 is not an Omega Prime as 4 (which is a perfect square) is a divisor of 12. Carl decides to play a bit more with Omega Primes. He has an array A of integers. Carl wants to find the number of different subsets such that the product of elements in each subset is an Omega Prime. Help Carl find this number. The input consists of an integer array A . Since the number of subsets can be large, return the answer modulo 10 9 + 7. Examples Example 1: Input: A = [2, 4, 3] Output: 3 Explanation: The full explanation text for this example is cut off in the provided image. Example 2: Input: A = [2, 2, 2] Output: 3 Explanation: The f