sugubatz

Cosmin se plictisea la ora de limba și literatura română, când domnul profesor le-a spus elevilor faptul că în opera „Povestea lui Harap-Alb” există un personaj șugubăț. În acel moment, Cosmin și-a adus aminte de o problemă șugubeață pe care nu știe să o rezolve. În schimb, dacă îl veți ajuta să rezolve problema, vă va trimite prin poștă un spiriduș șugubăț, care are o vioară și un arcuș. Astfel, Cosmin va înțelege felul în care se rezolvă problema, iar voi vă veți bucura de muzică armonioasă.

Cerință

Se dau două numere, $N$ și $X$, urmate de un șir $A$ de $N$ numere naturale nenule, indexat de la $1$ la $N$. Se va construi un nou șir $B$, unde fiecare număr $b_i$ ($1 \leq i \leq N$) ia cea mai mare valoare a celui mai mare divizor comun pe care $a_i$ îl are cu un alt număr din șirul $A$. Să se determine numărul de subsecvențe din șirul $B$ care au suma "sau" pe biți mai mare sau egală cu numărul $X$.

O subsecvență din șirul $B$ este o înșiruire de elemente de pe poziții diferite, consecutive.

Suma "sau" pe biți a unei subsecvențe $v_1, v_2, \dots, v_k$ este definită ca $v_1 \vert v_2 \vert \dots \vert v_k$, unde $\vert$ semnifică operatorul "sau" pe biți.

Date de intrare

Pe prima linie se vor găsi numerele naturale $N$ și $X$, iar pe a doua linie se vor găsi cele $N$ numere naturale ale șirului $A$. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Se va afișa un singur număr ce reprezintă numărul de subsecvențe cu proprietatea cerută.

Restricții și precizări

• $2 \leq N \leq 1 \ 000 \ 000$;
• $1 \leq X \leq 1 \ 000 \ 000$;
• $1 \leq a_i \leq 1 \ 000 \ 000$.

Observație

Datorită datelor de intrare foarte mari, se vor folosi instrucțiunile următoare la începutul funcției main() în programul C++:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplu

stdin

5 3
17 2 9 12 2

stdout

12

Explicație

După ce fiecare număr $b_i$ ($1 \leq i \leq N$) ia cea mai mare valoare a celui mai mare divizor comun pe care $a_i$ îl are cu un alt număr din șirul $A$, șirul $B$ are valorile $1, 2, 3, 3, 2$. În acest nou șir există $12$ secvențe care au suma "sau" pe biți mai mare sau egală cu $3$.