Joseph loves questions with arrays! His friend Nick gave him interesting problem!
Initially, there is an array with n positive integers, numbered 1 through n. Let quality be a multiplication of all integers from the array. More formally, quality = a1 * a2 * a3 * ... * an. Nick is interested in number of arrays with size of k with same quality.
Of course, Joseph found that this problem is really hard for him. So, he needs your help.
The first line contains a single integer n and k — the number of positive integers in the array and the size of the arrays you have to count, respectively.
The next line contains n integers a1, a2, ..., an — an array which was described above.
Print the answer modulo 109 + 7.
Note: The numbers in all k-sized arrays must be positive.
The quality of an array is equal to 3 * 2 = 6, so there are 9 arrays with size 3 and quality is 6.