Neştiind ce poveste să găsească pentru această problemă, autorul a decis să nu mai complice concurenţii cu texte inutile, care mai mult te încurcă atunci când citeşti cerinţa.

Astfel se dă un şir de $N$ numere naturale. Se cere să se determine numărul de subsecvenţe ale şirului, cu proprietatea că cmmdc-ul subsecvenţei este divizibil cu un număr natural $P$. Super simplu.

Astfel se dă un şir de N numere naturale. Se cere să se determine numărul de subsecvenţe ale şirului, cu proprietatea că cmmdc-ul subsecvenţei este divizibil cu un număr natural P. Super simplu.

Prin subsecvenţă se înţelege o succesiune de unul sau mai multe elemente aflate pe poziţii consecutive în şirul iniţial.
h2. Date de intrare

Fişierul de intrare $aiacucmmdc.in$ conţine pe prima linie un număr natural $N$ (acesta reprezentând numărul de elemente ale şirului) şi numărul natural $P$.
Pe următoarea linie se află $N$ numere naturale separate prin spaţiu, reprezentând elementele şirului.

Fişierul de intrare $aiacucmmdc.in$ conţine pe prima linie un număr natural N (acesta reprezentând numărul de elemente ale şirului) şi numărul natural P.
Pe următoarea linie se află N numere naturale separate prin spaţiu, reprezentând elementele şirului.

h2. Date de ieşire

În fişierul de ieşire $aiacucmmdc.out$ va conţine pe prima linie un număr natural $K$, acesta reprezentând numărul de subsecvenţe cu proprietatea cerută.

În fişierul de ieşire $aiacucmmdc.out$ va conţine pe prima linie un număr natural K, acesta reprezentând numărul de subsecvenţe cu proprietatea cerută.

h2. Restricţii
* Prin cmmdc se înţelege cel mai mare divizor comun comun al numerelor respective.
* Prin definiţie, cel mai mare divizor comun al unui singur număr este chiar numărul însuşi.

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ a[i], P ≤ 2.000.000.000$
* Pentru teste în valoare de $10$ puncte $N ≤ 250$
* Pentru teste în valoare de $25$ de puncte $N ≤ 3000$
* Pentru teste în valoare de $50$ de puncte $N ≤ 10.000$ şi numărul de subsecvenţe nu va depăşi $1.500.000$
* Pentru teste în valoare de $90$ de puncte $N ≤ 1.000.000$
* Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.

* 1 <= N <= 1.000.000
* 1 <= a[i], P <= 2.000.000.000
* Pentru teste în valoare de 10 puncte N <= 250
* Pentru teste în valoare de 25 de puncte N <= 3000
* Pentru teste în valoare de 50 de puncte N <= 10.000 şi numărul de subsecvenţe nu va depăşi 1.500.000
* Pentru teste în valoare de 90 de puncte N <= 1.000.000
* Se vor acorda 10 puncte din oficiu

h2. Exemplu
table(example). |_. aiacucmmdc.in |_. aiacucmmdc.out |

| 6 3
2 9 6 4 3 13
| 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

* $N = 6, P = 3$
* Cele $4$ subsecvenţe sunt:
* de la $2$ la $2 = {9} cu cmmdc = 9$
* de la $3$ la $3 = {6} cu cmmdc = 6$
* de la $2$ la $3 = {9, 6} cu cmmdc = 3$
* de la $5$ la $5 = {3} cu cmmdc = 3$

...

== include(page="template/taskfooter" task_id="aiacucmmdc") ==

== include(page="template/taskfooter" task_id="aiacucmmdc") ==