Count Ways To Make Array With Product

Moderate

0/80

Average time to solve is 30m

Contributed by

3 upvotes

Asked in companies

Problem statement

There are two friends Ranbir and Alia. Ranbir gave a question to Alia that you are given ‘Q’ queries in the form [N, P].

For each query, Alia has to count how many arrays consisting of positive integers of size ‘N’ she could build such that the product of all the array elements is equal to ‘P’.

Since the answer could be large, return the answer to each query modulo 10^9 + 7.

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

Input format :

The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test contains an integer ‘Q’ denoting the total number of Queries.

Then each of the next ‘Q’ lines contains two space-separated integers ‘N’ and ‘P’ denoting the size of the array to be formed and the product it should have after the array is formed respectively.

Output format :

For each test case, print the count of arrays formed for each query in a single line.

Output for each test case is printed on a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= Q <= 10^4
1 <= N , P <= 10^4

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

4 1
1

Explanation For Sample Input 1 :

For the first test case, consider each query independently

For the first query where we have to build an array of size 2 and the product of array, elements should be equal to 6. So all the possible arrays are: {1, 6}, {6, 1}, {2, 3} and {3, 2}. Therefore, the answer will be 4 for the given query.

For the second query where we have to build an array of size 1 and the product of the array, elements should be equal to 1. So the only possible array is {1}. Therefore, the answer will be 1 for the given query.

For the second test case, consider each query independently

For the first query where we have to build an array of size 5 and the product of array elements should be equal to 1. So the only possible array is {1, 1, 1, 1, 1}. Therefore, the answer will be 1 for the given query.

Sample Input 2 :

Sample Output 2 :

196 2
9 6

Console