Count Sequences With Product X Problem Statement

You are provided with an array NUM containing N positive integers. Your objective is to find the total number of possible sequences of positive integers (greater than 1) whose product equals X.

Explanation:

The value of X is computed as the product of N terms, where each ith term is represented by the ith prime number raised to the power of the ith element in the given array.

In mathematical terms, X can be expressed as:

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

Input:

The first line of input contains an integer T, representing the number of test cases.
Then, T test cases follow.
Each test case begins with a line containing a single integer N, the size of the array NUM.
The subsequent line contains N space-separated integers, the elements of NUM.

Output:

For each test case, output a single integer on a new line representing the total number of possible sequences of positive integers (greater than 1) whose product equals X. 

Example:

Input: 
2
3
1 2 1
2
1 1

Output: 
6
3

Constraints:

• The sum of all elements in array NUM will always be ≤ 400.
• The answer should be printed modulo 1000000007, due to potentially large sizes.
• 1 ≤ T ≤ 10
• 2 ≤ N ≤ 500
• 1 ≤ NUM[i] < 100
• Time Limit: 1 second

Note:

You are not required to print anything explicitly. Simply implement the desired function, and it will handle the output.