Adott egy \(A\) sorozat \(N\) természetes számmal. Kiszámítani a maradékot, amelyet úgy kapunk, hogy az \(A\) sorozat összes \(N!\) számú permutációja szomszédos tagjai legnagyobb közös osztójának összegét elosztjuk a \(10^9 + 7\) számmal .

Más szóval, ha \(S_N\) az összes \(N\) hosszúságú permutáció halmaza, kiszámítani a \(\sum_{P \in S_N} \sum_{i=1}^{N-1} NZD(A_{P_i}, A_{P_{i+1}})\) összeg \(10^9+7\) értékkel alkotott modulusát! (A NZD a legnagyobb közös osztó rövidítése.)

Bemenet

A szabványos bemenet első sorában az \(N\) szám áll. A következő sorban \(N\) természetes szám, az \(A\) sorozat áll.

Kimenet

A megoldást kiíratni a szabványos kimenetre!

Korlátozások

• \(1 \leq N \leq 10^5\)
• \(1 \leq A_i \leq 10^6\)

Alfeladatok

1. (11 pont) \(N \leq 9\).
2. (17 pont) \(N \leq 1000\).
3. (21 pont) \(A_i \leq 1000\).
4. (6 pont) Az\(A\) sorozatban legfeljebb két különböző érték van.
5. (45 pont) Nincsenek külön korlátozások.

1. példa

Bemenet

3
12 15 15

Kimenet

84

Magyarázat

\(6\) permutációra keressük az összeget.

• \([12, 15, 15]\), \(3 + 15 = 18\)
• \([12, 15, 15]\), \(3 + 15 = 18\)
• \([15, 12, 15]\), \(3 + 3 = 6\)
• \([15, 15, 12]\), \(15 + 3 = 18\)
• \([15, 12, 15]\), \(3 + 3 = 6\)
• \([15, 15, 12]\), \(15 + 3 = 18\)

A megoldás \(18 + 18 + 6 + 18 + 6 + 18 = 84\).

2. példa

Bemenet

7
20 25 9 10 21 29 12

Kimenet

69120