inno

Se dau numerele naturale $N$ și $K$, precum și un șir $a_1$, $a_2$, $\dots$, $a_N$ de numere naturale nenule. Din șir se poate elimina o singură secvență (eventual vidă) $a_i$, $a_{i + 1}$, $\dots$, $a_j$ astfel că în șir rămân elementele $a_1$, $a_2$, $\dots$, $a_{i − 1}$, $a_{j + 1}$, $\dots$, $a_N$. De exemplu, din șirul $a$ = [$1$, $2$, $3$, $4$, $5$, $7$] se poate elimina secvența $3$, $4$, $5$ și rămâne $1$, $2$, $7$; sau se poate elimina secvența vidă și rămâne șirul inițial $1$, $2$, $3$, $4$, $5$, $7$; sau se poate elimina $1$, $2$, $3$, $4$ și rămâne șirul $5$, $7$.

După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația & pe biți asupra lor, rezultatul este un număr care are cel puțin $K$ biți de $1$ în baza $2$. De exemplu, dacă $a$ = ($1$, $2$, $3$, $4$, $5$, $7$) și $K = 2$, atunci prin eliminarea secvenței $1$, $2$, $3$, $4$ rămân elementele $5$, $7$, iar $5$ & $7$ = $5$, care are $2$ biți de $1$ în baza $2$. Dar dacă se elimină secvența $3$, $4$, $5$ atunci rămân elementele $1$, $2$, $7$, iar $1$ & $2$ & $7$ = $0$, deci nu este șir inno.

Cerință

Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.

Date de intrare

Fișierul de intrare inno.in conține pe prima linie numerele naturale $N$ și $K$. Pe linia a doua se află $N$ numere naturale reprezentând elementele șirului, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire inno.out va conține pe prima linie un singur număr natural reprezentând numărul de moduri de a elimina o secvență astfel încât șirul rămas să fie inno.

Restricții și precizări

• $3 \leq N \leq 200 \ 000$
• $1 \leq K \leq 29$
• $0 \leq a_i \leq 2^{31} − 1$
• & este operatorul de conjuncție pe biți. Dacă $x$ și $y$ sunt valori binare, atunci expresia $x$ & $y$ este egală cu $1$ dacă și numai dacă $x = 1$ și $y = 1$. Deci $1$ & $1$ = $1$, $0$ & $1$ = $0$, $1$ & $0$ = $0$, $0$ & $0$ = $0$. Dacă $a$ și $b$ sunt numere naturale, atunci expresia $a$ & $b$ se efectuează la nivelul reprezentării în baza $2$. De exemplu, dacă $a = 12$ și $b = 20$, atunci: $a$ & $b$ = $12$ & $20$ = $01100_{2}$ & $10100_{2}$ = $00100_{2}$ = $4_{10}$
• Pentru teste în valoare de $12$ puncte: $1 \leq K \leq 2$ și $3 \leq N \leq 25$
• Pentru alte teste în valoare de $23$ de puncte: $500 \leq N \leq 8 \ 000$
• Pentru alte teste în valoare de $65$ de puncte: Nu există restricții suplimentare.

Exemplul 1

inno.in

4 2
10 7 5 15

inno.out

5

Explicație

Pentru primul exemplu modalitățile sunt:

• se elimină $10$ și rămâne șirul $7$, $5$, $15$, iar $7$ & $5$ & $15$ = $5$, care are $2$ biți de $1$
• se elimină $10$, $7$ și rămâne șirul $5$, $15$, iar $5$ & $15$ = $5$, care are $2$ biți de $1$
• se elimină $10$, $7$, $5$ și rămâne șirul $15$, iar $15$ are $4$ biți de $1$
• se elimină $7$, $5$ și rămâne șirul $10$, $15$, iar $10$ & $15$ = $10$ are 2 biți de $1$
• se elimină $7$, $5$, $15$ și rămâne șirul $10$, iar $10$ are $2$ biți de $1$

Exemplul 2

inno.in

5 4
7 7 6 1 62

inno.out

1

Explicație

Pentru cel de-al doilea exemplu singura posibilitate este eliminarea secvenței $7 \ 7 \ 6 \ 1$. Rămâne doar numărul $62$, care are $5$ biți de $1$.