Joseph and Array
Tag(s):

Combinatorics, Easy-Medium, Math, Modular arithmetic

Problem
Editorial
Analytics

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

• Subtask #1 (10 points) : n, k <=10 and the quality <= 10
• Subtask #2 (90 points) : Original constraints
SAMPLE INPUT
2 3
2 3
SAMPLE OUTPUT
9

Explanation

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)
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...