Moses is planning something and needs your help. Moses has recently been admitted to the Computer Science program at the University of Waterloo. However, the University of Waterloo has been notified that many of their new students enrolled in the Computer Science program are unworthy. To distinguish between the worthy and the unworthy, all applicants have received a math entrance exam. Moses, who is an excellent student, has correctly completed all problems except the last one. He knows that solving all problems will guarantee acceptance to the University of Waterloo but despite being talented in every way possible, Moses is unable to solve the last problem and he requires your help to do so.

Moses is given a function ~f(x,y)~ where ~f(x,y)~ is defined if ~1 \le y \le x \le N~ ~(1 \le N \le 10^6)~. All ~f(x,y)~ that is defined will have integer values.

For all pairs of integers ~(x,y)~ such that ~1 \le y \le x \le N-1~, ~f(x,y)~ also has the property that ~k \times f(x,y) = f(x+1,y) \times f(x+1,y+1)~ where ~k = b^p~ for some positive integer ~b~ and ~p~ ~(2 \le p \le 5 \times 10^3)~ such that ~b~ is maximized.

In other words, to calculate ~f(x,y)~, first find the product of ~f(x+1,y)~ and ~f(x+1,y+1)~. Then, divide the largest factor that can be represented as ~b^p~ for some positive integer ~b~ and ~p~, where the result is minimized.

He is also given the values ~a_i~ ~(1 \le i \le N)~ where ~f(N,i) = a_i~.

Moses needs your help to calculate the value ~f(1,1)~, modulo ~10^9+7~.

Constraints

~1 \le N \le 10^6~

~1 \le a_i \le 10^6~

~2 \le p \le 5 \times 10^3~

~p~ is guaranteed to be prime.

Subtask 1 [10%]

~1 \le N \le 100~

~2 \le p \le 100~

~1 \le a_i \le 100~

Subtask 2 [10%]

~1 \le N < p \le 5 \times 10^3~

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line of the input contains ~N~ ~(1 \le N \le 10^6)~ and ~p~ ~(1 \le p \le 5 \times 10^3)~.

The next line contains ~N~ integers, the ~i^\text{th}~ of which is ~a_i~.

Output Specification

Output ~f(1,1)~, modulo ~10^9+7~.

Sample Input 1

4 2
24 15 7 3

Sample Output 1

210