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 1yxN (1N106). All f(x,y) that is defined will have integer values.

For all pairs of integers (x,y) such that 1yxN1, f(x,y) also has the property that k×f(x,y)=f(x+1,y)×f(x+1,y+1) where k=bp for some positive integer b and p (2p5×103) 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 bp for some positive integer b and p, where the result is minimized.

He is also given the values ai (1iN) where f(N,i)=ai.

Moses needs your help to calculate the value f(1,1), modulo 109+7.

Constraints

1N106

1ai106

2p5×103

p is guaranteed to be prime.

Subtask 1 [10%]

1N100

2p100

1ai100

Subtask 2 [10%]

1N<p5×103

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line of the input contains N (1N106) and p (1p5×103).

The next line contains N integers, the ith of which is ai.

Output Specification

Output f(1,1), modulo 109+7.

Sample Input 1

Copy
4 2
24 15 7 3

Sample Output 1

Copy
210

Comments

There are no comments at the moment.