Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Дат је низ \(A\) од \(N\) природних бројева. Израчунати остатак који при дељењу са \(10^9 + 7\) даје збир највећих заједничких делилаца суседних чланова свих \(N!\) пермутација низа \(A\).

Другим речима, ако је \(S_N\) скуп свих пермутација дужине \(N\), израчунати \(\sum_{P \in S_N} \sum_{i=1}^{N-1} NZD(A_{P_i}, A_{P_{i+1}})\) по модулу \(10^9+7\).

Опис улаза

У првом реду стандардног улаза налази се број \(N\). У наредном реду налази се \(N\) природних бројева, низ \(A\).

Опис излаза

Исписати решење на стандардни излаз.

Ограничења

Подзадаци

  1. (11 поена) \(N \leq 9\).
  2. (17 поена) \(N \leq 1000\).
  3. (21 поена) \(A_i \leq 1000\).
  4. (6 поена) У низу \(A\) има највише две различите вредности.
  5. (45 поена) Нема додатних ограничења.

Пример 1

Улаз

3
12 15 15

Излаз

84

Објашњење

Тражимо збир за \(6\) пермутација: - \([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\)

Решење је \(18 + 18 + 6 + 18 + 6 + 18 = 84\).

Пример 2

Улаз

7
20 25 9 10 21 29 12

Излаз

69120