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ța

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 1.000.000.009.

Date de intrare

Pe prima linie din fișierul de intrare countall.in 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

Fișierul de ieșire countall.out va conține pe prima linie numărul S, reprezentând restul împărțirii la 1.000.000.009 a sumei valorilor count pentru toate șirurile care se pot obține din șirul A.

Restricții și precizări

• 1 ≤ N, M ≤ 100.000
• 0 ≤ A[i] ≤ M, pentru orice i de la 1 la N
• Pentru 13 puncte, 1 ≤ N,M ≤ 7
• Pentru 8 puncte, M = 2
• Pentru 21 puncte, șirul A nu conține nicio valoare de 0
• Pentru 23 puncte, șirul A conține doar valori de 0
• Pentru 17 puncte, 1 ≤ N, M ≤ 1.000
• Pentru 18 puncte, fără restricții suplimentare

Exemplul 1:

countall.in

3 4
2 0 3

countall.out

9

Explicație

Ș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.

Exemplul 2:

countall.in

3 2
0 0 2

countall.out

7

Explicație

Ș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.