Given a $n$ elements array $A_1,A_2,...,A_n$.Calculate:
$$\prod gcd(S)$$
with $S$ are non-empty subsets of given array$A$.
### Input
- The first line contains integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the answer, modulo $10^9+7$.
### Constraints
- $1 \le n \le 10^5.$
- $1 \le A_1,A_2,...,A_n \le 10^6.$
### Example
Input:
```
4
2 3 1 6
```
Output:
```
216
```
