Pentru un număr natural x, vom nota cu B(x) numărul biţilor de 1 din reprezentarea lui x în baza 2. De exemplu, B(6) = 2, B(15) = 4, B(16) = 1. Fie un şir de N numere naturale x₁, x₂, ..., x_N. Pentru orice două valori i şi j, cu 1 <= i <= j <= N, vom nota prin B(i, j) = B(x_i) + B(x_i+1) + ... + B(x_j), adică B(i, j) este numărul tuturor biţilor de 1 din secvenţa de numere x_i, x_i+1, x_i+2, ..., x_j.

Cerinţă

Dat şirul x₁, x₂, ..., x_N şi un număr natural T, să se determine numărul secvenţelor de forma x_i, x_i+1, x_i+2, ..., x_j cu proprietatea că B(i,j) = T.

Date de intrare

Fişierul secvb.in conţine pe prima linie numerele naturale N şi T, separate printr-un spaţiu. Pe linia a doua se găsesc N numere naturale x₁, x₂, ..., x_N separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire secvb.out va conţine un singur număr natural reprezentând numărul de secvenţe din şir care au numărul biţilor de 1 egal cu T.

Restricţii

• 1 <= N <= 50 000
• 0 <= T <= 100 000
• valorile din şir sunt numere naturale cuprinse între 1 şi 1000

Exemplu

secvb.in	secvb.out	Explicaţii
7 6 8 3 7 14 10 63 1	3	Sunt trei secvenţe având în total 6 biţi de 1: 8 3 7 7 14 63

prof. Dan Pracsiu

Grupul Şcolar "Ştefan Procopiu" Vaslui

dpracsiu@yahoo.com