countall

Kida vă oferă două numere $N$ și $M$. Ea vă mai oferă și un șir $A$, de $N$ numere naturale cuprinse între $0$ și $M$ inclusiv. Șirul $A$ conține două tipuri de valori: valori cuprinse între $1$ și $M$, care nu pot fi schimbate, respectiv valori de $0$, care pot fi înlocuite cu orice număr cuprins între $1$ și $M$.

Pentru un șir $V$ cu valori între $1$ și $M$, vom nota cu $count(V)$ numărul de perechi $(V_i, V_j)$ de pe pozițiile $i$ și $j$ astfel încât $i < j$ și $cmmdc(V_i, V_j) = 1$.

Cerință

Se cere suma $count(V)$ pentru toate șirurile distincte $V$ care se pot obține din șirul $A$, înlocuind toate valorile de $0$ cu numere cuprinse între $1$ și $M$. Deoarece acest număr poate să fie foarte mare, se cere restul împărțirii sale la $10^9 + 9$.

Date de intrare

Pe prima linie din fișierul de intrare se află două numere $N$ și $M$, iar pe a doua linie valorile din șirul $A$, separate prin câte un spațiu.

Date de ieșire

Pe singura linie din fișierul de ieșire se află numărul $S$, reprezentând restul împărțirii la $10^9 + 9$ a sumei valorilor $count$ pentru toate șirurile care se pot obține din șirul $A$.

Restricții

• $1 \leq N,M \leq 100 \ 000$
• $0 \leq A_i \leq M$, pentru orice $i$ de la $1$ la $N$.

Exemple

countall.in

3 4
2 0 3

countall.out

9

Șirurile care se pot obține sunt:
$[2, 1, 3]$, pentru care valoarea $count$ este $3$;
$[2, 2, 3]$, pentru care valoarea $count$ este $2$;
$[2, 3, 3]$, pentru care valoarea $count$ este $2$;
$[2, 4, 3]$, pentru care valoarea $count$ este $2$;
Suma valorilor $count$ este $3 + 2 + 2 + 2 = 9$.

countall.in

3 2
0 0 2

countall.out

7

Șirurile care se pot obține sunt:
$[1, 1, 2]$, pentru care valoarea $count$ este $3$;
$[1, 2, 2]$, pentru care valoarea $count$ este $2$;
$[2, 1, 2]$, pentru care valoarea $count$ este $2$;
$[2, 2, 2]$, pentru care valoarea $count$ este $0$;
Suma valorilor $count$ este $3 + 2 + 2 + 0 = 7$.