Problem Description

This problem is translated from PA 2022 Round 5 Drzewa rozpinające.

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$.

Input Format

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 Format

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

4
1 2 3 4

24

Hint

For $100\%$ of the testdata, the Constraints are:

$1 \le n \le 5000$, $1 \le a_i \le 5000$.

Translated by ChatGPT 5