New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Unit Power Subsets

Contributed by

TanishkTonk

Hard

0/120

0 upvotes

Problem Statement

You are given an integer array ‘Arr’. You are required to calculate the number of subsets whose product can be represented as the product of unit powers of one or more distinct primes. As the answer can be large calculate it modulo (10^9+7).

Note: Subsets are considered distinct if the chosen set of indexes are different.

For Example:

Suppose arr = [1, 3, 9, 5]

Valid subsets are as follows:
[3], Product = 3.
[1, 3], Product = 1 * 3.
[5], Product = 5.
[1, 5], Product = 1 * 5.
[3, 5], Product = 3 * 5.
[1, 3, 5], Product = 1 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have six valid subsets, our output will be 6.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, denoting the size of ‘Arr’.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements of ‘Arr’.

Output Format:

For each test case, print a single integer value denoting the number of valid subsets modulo (10^9+7).

Print a separate line for each test case.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 20
1 ≤ ΣN ≤ 2 * 10^5

Time limit: 1 Sec

Sample Input 1 :

Sample Output 1 :

6
5

Explanation For Sample Input 1 :

For First Case - Same as explained in above example.

For the second case - 

arr = [14, 15, 2]
[14], Product = 2 * 7.
[15], Product = 3 * 5.
[2], Product = 2.
[14, 15], Product = 2 * 3 * 5 * 7.
[2, 15], Product = 2 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have five valid subsets, our output will be 6.

Sample Input 2 :

2
7
1 2 3 4 5 6 7
8
1 5 2 8 1 7 1 9

Sample Output 2 :

38
56

Auto

Console