신장 트리

길이가 $n$인 정수 수열 $a_1, a_2, \ldots, a_n$이 주어진다. 이 수열로 정점이 $n$개인 무방향 그래프를 만든다. 서로 다른 두 정점 $i$와 $j$ ($i \ne j$)는 $\gcd(a_i, a_j)$개의 서로 구별되는 간선으로 연결된다. 이 그래프의 신장 트리 개수를 구하라. 두 신장 트리는 한쪽에만 들어 있는 간선이 있으면 서로 다른 트리로 본다. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $n$ ($1 \le n \le 5000$)이 주어진다. 이는 수열의 길이이자 그래프의 정점 개수이다. 둘째 줄에 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 5000$)이 주어진다.

그래프의 신장 트리 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제의 그래프는 아래 그림과 같다.

이 그래프의 서로 다른 신장 트리는 정확히 24개이다.