Question

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

Answer 1

#include <stdio.h>
int c=0;
void product(int k,int i,int m)
{
    int j;
    if(k==0)
    {
        if(i<=m)
        {
            c++;
        return;
        }
    }
    else
    {
        if(i>m)
            return ;
        for(j=i;j<=m;j++)
        {
            if(m%j == 0)
                product(k-1,j,m/j);
        }
    }
}
int main()
{
   int n,k,a[10],m=1,i,j;
   scanf("%d%d",&n,&k);
   for(i=0;i<n;i++)
   {
       scanf("%d",&a[i]);
       m=m*a[i];
   }
   for(i=1;i<=m;i++)
   {
        if(m%i==0)
            product(k-2,i,m/i);
   }
   printf("%d\n",c);
   return 0;
}