nane

Nane

== include(page="template/taskheader" task_id="nane") ==

Nane de pe Jiu, mare algoritmician fiind, va provoaca sa rezolvati o problema prea usoara pentru el. Nane va da un N numere pozitive si un numar K. Acesta doreste sa ii spuneti cate subsecvente diferite au suma OR (operatia pe biti) a numerelor din subsecventa a carei reprezentare in binar are maxim K biti.

Nane de pe Jiu, mare algoritmician fiind, va provoaca sa rezolvati o problema prea usoara pentru el. Nane va da N numere pozitive si un numar K. Fie Sp suma OR (operatia pe biti) a numerelor unei subsecvente. Numim o subsecventa speciala daca Sp-ul subsecventei are in reprezentarea sa binara maxim K biti de 1. Nane va cere numarul de subsecvente speciale.
 
Doua subsecvente sunt diferite daca cel putin o pozitie din una nu se regaseste in celalata.
 

Dovediti-i lui Nane ca sunteti priceputi in ale algoritmicii si calculati numarul cerut!
h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $nane.out$ se va afla pe prima linie un singur numar Nr, reprezentand numarul cerut de Nane.

În fişierul de ieşire $nane.out$ se va afla pe prima linie un singur numar $Nr$, reprezentand numarul cerut de Nane.

h2. Restricţii
* $1 ≤ N ≤ 100.000$ ; $1 ≤ K ≤ 30$

* Pentru 20 puncte $1 ≤ N ≤ 50$
* Pentru alte 30 puncte $1 ≤ N ≤ 1.000$
* Toate cele N numere vor fi naturale < 2^30

* Pentru $20$ puncte $1 ≤ N ≤ 50$
* Pentru alte $30$ puncte $1 ≤ N ≤ 1.000$
* Toate cele N numere vor fi naturale si se pot reprezenta pe $30$ de biti

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

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

| 5 2
  2 14 3 2 10
| 6
|
| 7 3
  13 12 14 9 1 11 11
| 15

|
h3. Explicaţie

...

* Exemplu: subsecventa 2 6 are suma OR 6; 6 in binar este 110 (2 biti de 1). Aceasta subsecventa va fi numarata daca K>=2.
 
In primul exemplu, subsecventele sunt: (1), (3), (3,4), (4), (4,5) si (5)

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