26726번 - Drzewa rozpinające 다국어

문제

Dany jest ciąg n liczb całkowitych a₁, a₂, . . . , a_n. Z jego pomocą tworzymy nieskierowany graf na n wierzchołkach: wierzchołki i oraz j (dla i ≠ j) są połączone NWD(a_i, a_j) 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 10⁹ + 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 a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 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 10⁹ + 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.