Count sequences of positive integers having product X
You are given an array 'NUM' consisting of N positive Integers. Your task is to find the total number of possible sequences of positive integers (greater than 1) whose product is 'X'.

The value of 'X' is calculated as the product of the N terms, where the ith term is generated by raising the ith prime number to the power of an ith element in the given array.

In mathematical terms, we can write X as:

X = 2 ^ NUM[1] * 3 ^ NUM[2] * 5 ^ NUM[3] * 7 ^ NUM[4] * 11 ^ NUM[5] * … up to Nth term

Note :

1. Sum of all the elements in the array 'NUM' will always be less than or equal to 400. 2. As the total number of such sequences can be very large, print the answer modulo 1000000007.

Input Format:

The first line of input contains a single integer T, representing the number of test cases Then the T test cases follow. The first line of each test case contains a number N denoting the size of the array 'NUM'. The second line contains N space-separated integers, the elements of 'NUM'.

Output format:

For each test case print in a new line, an integer representing the total number of possible sequences of positive integers (greater than 1) whose product is X.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1

Question

Count sequences of positive integers having product X

You are given an array 'NUM' consisting of N positive Integers. Your task is to find the total number of possible sequences of positive integers (greater than 1) whose product is 'X'.

The value of 'X' is calculated as the product of the N terms, where the ith term is generated by raising the ith prime number to the power of an ith element in the given array.

In mathematical terms, we can write X as:

X = 2 ^ NUM[1] * 3 ^ NUM[2] * 5 ^ NUM[3] * 7 ^ NUM[4] * 11 ^ NUM[5] * … up to Nth term

Note :

1. Sum of all the elements in the array 'NUM' will always be less than or equal to 400.
2. As the total number of such sequences can be very large, print the answer modulo 1000000007.

Input Format:

The first line of input contains a single integer T, representing the number of test cases
Then the T test cases follow.

The first line of each test case contains a number N denoting the size of the array 'NUM'.

The second line contains N space-separated integers, the elements of 'NUM'.

Output format:

For each test case print in a new line, an integer representing the total number of possible sequences of positive integers (greater than 1) whose product is X.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1<= T <=10
2 <= N <= 500
1 <= NUM[i] < 100
Time Limit : 1 sec

Accepted Answer

Combinatorics

The idea is to make use of a combinatorics approach to find the contribution made by each element of the array in a total number of sequences.

The maximum number of positive integers in a sequence can be equal to the total sum of array elements, as explained below.
If given array is {1,1} then :
- {1,1} = 2^1 * 3^1 = 6 so we can have a maximum 2 prime whose product is 6.
Let's say the total sum of array elements is S.
We will make an array of integers say ANS[S+1], initialize to zero, which will store the contribution made by ith array element to a total number of sequences.
We will also make a 2-D array of integers say BCOFF[500][500], BCOFF will store permutations of binomial coefficients.
Then use dynamic programming to fill the slots in the possible sequences starting from index 1 to S.
For each j-th prime number having power as ARR[j], divide all the ARR[j] primes into each of the i slots.
Use the Combinatorics Approach to divide ARR[j] elements into i slots.
Store the value in array ARR such that ARR[i] is updated as follows:
- ARR[i]= ARR[i] * (ARR[j]+i-1)C(i-1).
Here we are using nCr, which is the method of selection of ‘r’ objects from a set of ‘n’ objects where the order of selection does not matter.
We can find this value from BCOFF array, or we can say : ARR[i]= ARR[i] * BCOFF[ ARR[j]+i-1 ][ i-1].
However, ANS will also contain the sequences with one or more than 1 slot empty, hence subtract the exact contribution for all slots where the number of slots filled is less than i.
For each of the slots from j = 1 to i-1, select j slots from i and subtract its contribution and update ARR[i] as ARR[i] = ARR[i]-BCOFF[i][j].
Now the sum of ANS elements will be our answer.

Let’s understand with an example:

Let’s take an example {1,0,1}:
Then the value of X = 2^1*3^0*5^1 = 10 .
Now as the sum of the array is 2 (S=2), there can be a maximum of 2 numbers in sequences whose product is 10.
ANS[3]= {0,0,0}.
We will run a loop for i = 1 to i = 3 and inside this loop, we will run a loop for j = 0 to j < 2 and :
- ANS[i]=1 and then ANS[i] will be multiplied by (ARR[j]+i-1)C(i-1), here we are dividing ARR[j] + i - 1 into i - 1 slots.
- But ARR[i] will also contain the sequences with one or more than 1 slot empty, so to get the exact contribution we will do:
  - ANS[i] = ANS[i]- ANS[i]*(iCj).
After completion of the above step, ANS will be [0,1,2] which will add up to 3.
So our answer will be 3.

Space Complexity: OtherExplanation:

O(S), where ‘S’ is the sum of all the elements of the ‘NUM’ array.

We are using ‘ANS’ array/list of size ‘S’ and ‘BCOFF’ array of constant size. Hence, the overall space complexity is O(S).

Time Complexity: OtherExplanation:

O(N * S), where N is the size of ‘NUM’ array/list and ‘S’ is the sum of all the elements of the given array.

As we are running two nested loops where the outer loop runs for ‘S’ times and the inner loop runs for ‘N’ times.

C++ (g++ 5.4)

/*

    Time complexity: O(N * S)

    Space complexity: O(S),



    Where N is the size of the given 'NUM' array/list and 

    S is the sum of all the elements in 'NUM'.

*/



int countSequence(const vector < int > & num) {



    int mod = 1000000007;



    int bcoff[501][501];



    bcoff[0][0] = 1;



    // Computing bcoffomial coefficients



    for (int i = 1; i <= 500; i++) {



        bcoff[i][0] = 1;



        for (int j = 1; j <= i; j++) {

            bcoff[i][j] = (bcoff[i - 1][j] + bcoff[i - 1][j - 1]) % mod;

        }

    }

    // Calculating maximum length of sequence.

    int s = 0;



    for (int i = 0; i < num.size(); i++) {

        s += num[i];

    }



    vector < long long int > ans(s + 1);



    for (int i = 1; i <= s; i++) {



        ans[i] = 1;



        for (int j = 0; j < num.size(); j++) {

            ans[i] = (ans[i] * bcoff[num[j] + i - 1][i - 1]) % mod;

        }



        for (int j = 1; j < i; j++){

            ans[i] = (ans[i] - ((ans[j] * bcoff[i][j]) % mod) + mod) % mod;

        }

    }



    // Total possible sequences.

    int total = 0;



    for (int i = 0; i <= s; i++) {

        total = (ans[i] + total) % mod;

    }



    return total;

}

Python (3.5)

'''

    Time complexity: O(N * S)

    Space complexity: O(S),



    Where N is the size of the given 'NUM' array/list and 

    S is the sum of all the elements in 'NUM'.

'''



def countSequence(num):



    mod = 1000000007



    bcoff = [[0 for i in range(501)] for j in range(501)]



    bcoff[0][0] = 1



    # Computing bcoffomial coefficients



    for i in range(1, 501):



        bcoff[i][0] = 1



        for j in range(1, i + 1):

            bcoff[i][j] = (bcoff[i - 1][j] + bcoff[i - 1][j - 1]) % mod

        

    # Calculating maximum length of sequence.

    s = 0

    for i in range(len(num)):

        s += num[i]

    

    ans = [0] * (s + 1)



    for i in range(1, s + 1):



        ans[i] = 1



        for j in range(len(num)):

            ans[i] = (ans[i] * bcoff[num[j] + i - 1][i - 1]) % mod

        

        for j in range(1, i):

            ans[i] = (ans[i] - ((ans[j] * bcoff[i][j]) % mod) + mod) % mod



    # Total possible sequences.

    total = 0



    for i in range(s + 1):

        total = (ans[i] + total) % mod

    

    return total

Java (SE 1.8)

/*

    Time complexity: O(N * S)

    Space complexity: O(S),



    Where N is the size of the given 'NUM' array/list and 

    S is the sum of all the elements in 'NUM'.

*/



import java.util.ArrayList;



public class Solution {



    private static int mod = 1000000007;

    private static int[][] bcoff = new int[501][501];



    public static int countSequence(ArrayList < Integer > num) {

        bcoff[0][0] = 1;



        // Computing bcoffomial coefficients.

        for (int i = 1; i <= 500; i++) {

            bcoff[i][0] = 1;

            for (int j = 1; j <= i; j++) {

                bcoff[i][j] = (bcoff[i - 1][j] + bcoff[i - 1][j - 1]) % mod;

            }



        }



        // Calculating maximum length of sequence.

        int s = 0;

        for (int i = 0; i < num.size(); i++) {

            s += num.get(i);

        }



        long[] ans = new long[s + 1];



        for (int i = 1; i <= s; i++) {

            ans[i] = 1;

            for (int j = 0; j < num.size(); j++) {

                ans[i] = (ans[i] * bcoff[num.get(j) + i - 1][i - 1]) % mod;

            }



            for (int j = 1; j < i; j++) {

                ans[i] = (ans[i] - ((ans[j] * bcoff[i][j]) % mod) + mod) % mod;

            }



        }



        // Total possible sequences.

        long total = 0;

        for (int i = 0; i <= s; i++) {

            total = (ans[i] + total) % mod;

        }



        return (int) total;

    }

}