Moses Needs Help

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

Comments

There are no comments at the moment.