Let $N = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_n^{e_n}$, where $p_i$ are distinct prime numbers. Find:
The number of ways to represent $N$ as a product of $k$ numbers, i.e., $N = a_1 \cdot a_2 \cdot \dots \cdot a_k$. Find the number of distinct tuples $(a_1, a_2, \dots, a_k)$.
The number of ways to represent $N$ as a product of $k$ strictly increasing numbers, i.e., $N = a_1 \cdot a_2 \cdot \dots \cdot a_k$ where $a_1 < a_2 < \dots < a_k$. Find the number of distinct tuples $(a_1, a_2, \dots, a_k)$.
The number of ways to represent $N$ as a product of $k$ non-decreasing numbers, i.e., $N = a_1 \cdot a_2 \cdot \dots \cdot a_k$ where $a_1 \le a_2 \le \dots \le a_k$. Find the number of distinct tuples $(a_1, a_2, \dots, a_k)$.
The answers should be taken modulo $10^9 + 7$.
Input
The first line contains two integers $n$ and $k$.
The next line contains $n$ integers, $e_1, e_2, \dots, e_n$.
Output
Output three lines, each containing the answer to the corresponding question.
Constraints
- 10%, $n \le 10, e_i \le 10, k \le 2$
- 20%, $n \le 30, e_i \le 30, k \le 10$
- 10%, $n \le 30, e_i \le 30, k \le 20$
- 20%, $n \le 10000, e_i \le 10000, k \le 5$
- 20%, $n \le 10000, e_i \le 10000, k \le 15$
- 10%, $n \le 10000, e_i \le 10000, k \le 20$
- 10%, $n \le 10000, e_i \le 10000, k \le 25$
Examples
Input 1
5 3 3 4 2 5 1
Output 1
56700 9432 9468