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
Se vor acorda 10 puncte din oficiu

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

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

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

| 6 3
2 9 6 4 3 13
| 4

|
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") ==