Middle Earth Technical University is the place where all the engineers learn to build very powerful robots. Deroro is a very powerful engineer who can build very powerful robots. He wanted to calculate the power of the most powerful robot he can build only using every pure part once.

Deroro will use only one of each pure parts to build his robot. The total power of a robot is the multiplication of the power of pure robot parts which are used for building it.

Pure robot parts cannot be a combination of any 2 other parts.

• 6 Power robot part = Combination of the robot parts of power 2 and 3 (Not an essential part)
• 9 Power robot part = Combination of the robot parts of power 3 and 3 (Not an essential part)
• 21 Power robot part = Combination of the robot parts of power 3 and 7 (Not an essential part)
• 7 Power robot part = Is not a combination of any other 2 robot parts. (An essential robot part)

Given the powers of parts that Deroro can create can you find the power of the most powerful robot that Deroro can build only using every pure part once?

If Deroro knows how to create a part, it means that he already knows the parts which are needed to create that part.

Input

The first line contains the integer \(N\), the number of parts Deroro can create.

In the second line, there are \(N\) integers. Those are the powers of the parts Deroro can create.

• \(1 \leq \mathbf{N} \leq 10^5\)
• \(2 \leq \mathbf{A_i} \leq 10^{5}\)

Output

Output just one integer, the power of the most powerful robot that Deroro can build. Since this number can be very large, take modulo \(10^9+7\).

Examples

Input:

4
2 3 4 5

Output:

30

Input:

3
21 8 3

Output:

42