SP4195 MSE08H - GCD Determinant

我们称一个集合 $S = \{ x _ 1, x _ 2, \cdots, x _ n \}$ 是 factor-closed 的当且仅当对于任意 $x _ i \in S$，所有 $x _ i$ 的因子 $d$ 都满足 $d \in S$。考虑一个 gcd 矩阵 $S = (s _ {ij})$，其中 $s _{ij} = \gcd(x _ i, x _ j)$ 表示 $x _ i$ 与 $x _ j$ 的最大公因数。给出一个 factor-closed 的集合 $S$，求出该行列式的值： $$D _ n = \begin{vmatrix} \gcd(x _ 1, x _1) & \gcd(x _ 1, x _ 2) & \gcd(x _ 1, x _ 3) & \cdots & \gcd(x _ 1, x _ n) \\ \gcd(x _ 2, x _1) & \gcd(x _ 2, x _ 2) & \gcd(x _ 2, x _ 3) & \cdots & \gcd(x _ 2, x _ n) \\ \gcd(x _ 3, x _1) & \gcd(x _ 3, x _ 2) & \gcd(x _ 3, x _ 3) & \cdots & \gcd(x _ 3, x _ n) \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \gcd(x _ n, x _1) & \gcd(x _ n, x _ 2) & \gcd(x _ n, x _ 3) & \cdots & \gcd(x _ n, x _ n) \\ \end{vmatrix}$$

输入包含多组数据。对于每组数据，首先是一个整数 $n$（$0 < n < 1000$）表示 $S$ 中元素的数量。第二行包含 $S$ 中的数 $x _ 1, x _ 2, \cdots, x _ n$。显然每个 $x _ i$ 都是一个整数，$0 < x _ i < 2 \times 10 ^ 9$。保证输入的集合是正确的而且输入以 EOF 结尾。

对于每组数据，求出并输出 $D _ n \bmod 1000000007$ 的值。