Tính:
$$\prod gcd(S)$$
với $S$ là các tập con khác rỗng của mảng $A$ cho trước.
### Input
- Dòng đầu tiên gồm số nguyên $n$.
- Dòng thứ hai gồm $n$ số nguyên $A_i$.
### Output
- In ra một số nguyên là đáp án, modulo $10^9+7$.
### Ví dụ
Input:
```
1
1
```
Output:
```
1
```