Drzewa rozpinające

Dany jest ciąg n liczb całkowitych a1, a2, . . . , an. Z jego pomocą tworzymy nieskierowany graf na n wierzchołkach: wierzchołki i oraz j (dla i ≠ j) są połączone NWD(ai, aj) rozróżnialnymi krawędziami. Twoim zadaniem jest policzyć liczbę drzew rozpinających w zadanym grafie. Dwa drzewa uznajemy za różne, jeśli jedno z nich zawiera krawędź, której nie zawiera drugie. Jako, że liczba ta może być bardzo duża to wystarczy, że podasz jej resztę z dzielenia przez 109 + 7.

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 5 000), oznaczająca długość ciągu, a zarazem liczbę wierzchołków grafu.

W drugim wierszu standardowego wejścia znajduje się ciąg n liczb całkowitych a1, a2, . . . , an (1 ≤ ai ≤ 5 000), opisany w treści zadania.

W jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita, oznaczająca resztę z dzielenia przez 109 + 7 liczby różnych drzew rozpinających opisanego grafu.

Wyjaśnienie przykładu: Graf w teście przykładowym wygląda następująco:

Łatwo policzyć, że zawiera on dokładnie 24 różne drzewa rozpinające.