Tập ~S = \{x_1, x_2, \dots, x_n\}~ là thừa số đóng (factor closed) nếu với mỗi ~x_i \in S~ và với mỗi ước số ~d~ của ~x_i~ ta có ~d \in S~. Xét ma trận ~GCD(S) = s_{ij}~, với ~s_{ij} = GCD(x_i, x_j)~ -- USCLN của ~x_i~ và ~x_j~. Cho một tập thừa số đóng, hãy tính định thức của nó. (Kiến thức đại học).

Input

Gồm vài test case, mỗi test case bắt đầu là ~1~ số nguyên ~n~ ~(0 < n < 1000)~, số phần tử của ~S~. Dòng tiếp theo là ~n~ số của ~S~: ~x_1~, ~x_2~, ..., ~x_n~, ~0 < x_i < 2 \times 10^{9}~.

Output

VỚi mỗi test tính ~D_n \bmod 1000000007~. (~D_n~: định thức của test thứ ~n)~.

Sample Input

2 
1 2 
3 
1 3 9 
4 
1 2 3 6

Sample Output

1
12
4