Counting Spanning Trees in a GCD Multigraph

Given an integer sequence of length \(n\): \(a_1,a_2,\ldots,a_n\). Using this sequence, you can construct an undirected multigraph with \(n\) nodes. For every pair of distinct nodes \(i\) and \(j\), there are \(\gcd(a_i,a_j)\) distinguishable edges connecting them. Two spanning trees are considered different if one of them contains an edge that does not exist in the other. Your task is to calculate the number of spanning trees in this graph. Since the answer can be extremely large, output it modulo \(10^9+7\).

Matrix Tree Theorem: It is known that the number of spanning trees in any graph can be computed by forming its Laplacian matrix \(L\), where for every \(i\),

[ L_{ii} = \sum_{j \neq i} \gcd(a_i,a_j), \quad L_{ij} = -\gcd(a_i,a_j) \text{ for } i \neq j. ]

The number of spanning trees is equal to any cofactor of \(L\); that is, remove any row and the corresponding column and take the determinant of the resulting \((n-1) \times (n-1)\) matrix.

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 500\)), representing the number of nodes. The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output one integer: the number of spanning trees in the constructed graph modulo \(10^9+7\).

sample

2
1 1

1