To tydzień finałowy ostatniego roku studiów Busy Beavera i właśnie przypomniał sobie o liście aktywności do wykonania przed ukończeniem studiów, którą otrzymał podczas orientacji na pierwszym roku.
Dany jest ciąg $N$ liczb $a_1, \ldots, a_N$, gdzie $a_i$ reprezentuje radość z wykonania $i$-tej aktywności.
Ze względu na ograniczony czas na MIT, zdecydował się wykonać tylko spójny podciąg tych aktywności. Dodatkowo, aby jak najlepiej go wykorzystać, podciąg musi zawierać co najmniej dwie aktywności.
Podczas prokrastynacji w trakcie przygotowań do egzaminów końcowych wymyślił wyrafinowany sposób oceniania podciągu. Wynik podciągu od indeksu $l$ do $r$ to minimalna wartość XOR dwóch różnych aktywności. Formalnie, podciąg od indeksu $l$ do $r$ ma wynik $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$.
Ulubioną liczbą Busy Beavera jest $K$, więc chciałby obliczyć liczbę podciągów o wyniku $K$. Czy możesz mu pomóc?
Wejście
W pierwszej linii znajdują się dwie liczby całkowite $N$ oraz $K$ ($2 \le N \le 10^5$, $0 \le K < 2^{30}$).
W drugiej linii znajduje się $N$ liczb całkowitych oddzielonych spacjami $a_1, \dots, a_N$ ($1 \le a_i < 2^{30}$).
Wyjście
Wypisz jedną liczbę całkowitą: liczbę spójnych podciągów o rozmiarze co najmniej dwa, których wynik wynosi $K$.
Scoring
- ($15$ punktów) $N \leq 5000$.
- ($10$ punktów) $K = 0$.
- ($25$ punktów) Tablica $a$ jest posortowana niemalejąco ($a_{1} \leq \ldots \leq a_{N}$).
- ($50$ punktów) Brak dodatkowych ograniczeń.
Przykład
Wejście 1
5 2 1 3 1 4 5
Wyjście 1
3
Uwagi
Istnieją trzy podciągi, które należy policzyć:
- $l = 1, r = 2$.
- $l = 2, r = 3$.
- $l = 2, r = 4$.