Minimal Product Adjustment for Perfect Square Products

Father Study loves math very much. Given a sequence of integers \(a_1, a_2, \dots, a_n\), he wants to calculate another sequence of positive integers \(t_1, t_2, \dots, t_n\) such that:

• For every \(i\) with \(1 \le i \le n\), we have \(t_i > 0\).
• For every \(i\) with \(1 \le i < n\), the product \(a_i \times t_i \times a_{i+1} \times t_{i+1}\) is a perfect square. In other words, for every \(i\) (\(1 \le i < n\)) \[ a_i \cdot t_i \cdot a_{i+1} \cdot t_{i+1} = k^2 \quad \text{for some integer } k. \]
• The product \(\prod_{i=1}^{n} t_i\) is minimized.

Your task is to compute the minimum value of \(\prod_{i=1}^{n} t_i\) modulo \(10^9+7\).

Note on Mathematics: A positive integer is a perfect square if it is equal to the square of some integer. All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 10^5)\), representing the number of elements in the sequence.

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^9)\).

outputFormat

Output a single integer, the minimum value of \(\prod_{i=1}^{n} t_i\) modulo \(10^9+7\).

sample

2
2 3

6