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 = a₁ * a₂ * a₃ * ... * a_n. 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 a₁, a₂, ..., a_n — an array which was described above.

Output format

Print the answer modulo 10⁹ + 7.

Note: The numbers in all k-sized arrays must be positive.

Constraints

1 <= n, k <= 10⁵
1 <= a_i <= 10⁶

Subtasks

Subtask #1 (10 points) : n, k <=10 and the quality <= 10
Subtask #2 (90 points) : Original constraints