LDP - Try to learn properly

Most of the programmers like the problem description to be as short as possible, right? I also never like the problem description to be so narrative.

In this problem, you will be given an array a of n integers. If we multiply all the numbers of the array then we will get a result. Suppose the result is K.

Let's introduce another list of all the common multiples of an array as cmp. Definitely, the list has an infinite number of elements.

Suppose, we have an array a = {2, 3, 6}. The result of multiplication of 2, 3 and 6 is 36. So K = 36.

The 1st common multiple of a is 6, the 2nd common multiple is 12, 3rd is 18, and so on.

So the list, cmp = {6, 12, 18, 24, 30, 36, 42, ....... }.

Now the question is what the position of K in the cmp list? (1-based indexing)

As the result can be very big, you have to print K % 1000000009 (109 + 9), where % is modulo operator.

Note: In the above-described example, the position of  K is 6. (cmp6 = K = 36).

Input

The first line of the input will be n, the number of elements in the array.

In the next line, n elements of the array a1, a2, a3 ... an will be given.

Output

Print a single integer, the result of the problem described above with a new line.

Constraints

  • 0 < n ≤ 105
  • 0 < ai ≤ 109(1 ≤ i ≤ n)

Example

Input:
3
6 10 8

Output:
4

Added by:Prodip
Date:2019-03-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2022-04-01 02:36:51 Ishan
O(N*x*ln(x)) where x = no_of_prime(Sqrt(Max(Ai))); would give TLE
expected approach as prodipdatta7 said is O(N*x) .
But I dont think you can get that as simple two loops, if you can think of O(N*x*ln(x)) then think of improving the constraists to achieve amortised complexity of O(N*x)
2019-03-25 10:51:17
My complexity now is O(N * number_of_prime(sqrt(MaxValue(a))+number_of_prime(all value in array A)). Can it works?
2019-03-25 08:40:19
expected complexity is O(N * number_of_prime(sqrt(MaxValue(a)))
2019-03-25 08:16:58
what is the expected complexity of this problem? Cant find better than O(N*sqrt(MaxValueA))
2019-03-24 04:53:20
nadstratosfer I have updated the description
2019-03-24 02:30:25
Sample shows K = 480. How does that relate to the result of 4? Please rephrase the statement so that it makes sense.

Edit:
Thanks for clarification. Good problem, enjoyed solving.

Last edit: 2019-03-25 03:38:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.