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 (10⁹ + 9), where % is modulo operator.

Note: In the above-described example, the position of  K is 6. (cmp₆ = 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 a₁, a₂, a₃ ... a_n will be given.

Output

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

Constraints

• 0 < n ≤ 10⁵
• 0 < a_i ≤ 10⁹(1 ≤ i ≤ n)

Example

Input:
3
6 10 8
Output:
4