P9264 [PA 2022] Drzewa rozpinające

**This problem is translated from [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Round 5 [Drzewa rozpinające](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/drz/).** You are given an integer sequence of length $n$: $a_1,a_2,\ldots,a_n$. Based on this sequence, you can generate an undirected graph with $n$ vertices: between vertices $i$ and $j$ (for $i \neq j$), there are $\gcd(a_i,a_j)$ distinguishable edges connecting these two vertices. Your task is to compute the number of spanning trees of this graph. If, for two trees, one of them contains an edge that does not exist in the other, then these two trees are considered different. Since the number of spanning trees is very large, output it modulo $10^9+7$.

The first line contains an integer $n$, representing the length of the integer sequence. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the sequence.

Output one integer on a single line, representing the number of spanning trees of the generated graph modulo $10^9+7$.

For $100\%$ of the testdata, the Constraints are: $1 \le n \le 5000$, $1 \le a_i \le 5000$. Translated by ChatGPT 5