Array Product
Problem Description
You are given a list of N integers and another positive integer K. Write a program to compute the number of ways in which the product P of the given N integers can be expressed as a product of K positive integers (not necessarily distinct). The order of the factors in the expression is not important. For example, 1 x 2 x 3 and 2 x 3 x 1 are not counted as different ways of expressing 6 as a product of three integers.
Constraints
The product of the N integers <= 10^9
Each of the N integers <=5000
Input Format
Output
One line containing the number of ways in which the product of the N integers can be expressed as a product of K positive integers
Explanation
Example 1
Input
2 4
2 3
Output
2
Explanation
The product of the given integers is 6. This can be expressed as a product of 4 integers in 2 ways: 1x1x1x6, 1x1x2x3
Example 2
Input
2 3
4 16
Output
7
Explanation
The product is 64. This can be expressed as a product of three integers in the following ways:
1 x 1 x 64
1 x 2 x 32
1 x 4 x 16
1 x 8 x 8
2 x 2 x 16
2 x 4 x 8
4 x 4 x 4