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.
Input format
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.
Output format
Print the answer modulo 109 + 7.
Note: The numbers in all k-sized arrays must be positive.
Constraints
- 1 <= n, k <= 105
- 1 <= ai <= 106
Subtasks
- Subtask #1 (10 points) : n, k <=10 and the quality <= 10
- Subtask #2 (90 points) : Original constraints
The quality of an array is equal to 3 * 2 = 6, so there are 9 arrays with size 3 and quality is 6.
- (2, 1, 3), (2, 3, 1), (6, 1, 1)
- (1, 2, 3), (1, 6, 1), (3, 2, 1)
- (1, 1, 6), (1, 3, 2), (3, 1, 2)
