#include<iostream>
#include<string>

int main () {
		int n,k;
		std::string binary;
		std::cin >> n;
		std::cin >> k;
		std::cin >> binary;
	int number = 0;
	int max_num = 0;
	int pow =  1;		
	for (int i = binary.size() - 1 ; i >= 0; i-- ) {
		if (binary[i] == '1'){		
			number += pow; 
		
		}
max_num += pow;
		pow *= 2;
	}

	int counter = 0;
	for (int i = 0; i <= max_num; i++) {
		int tempCounter = 0;
		int temp = number + i;
		while(temp>0 && tempCounter <=k){
			
			if (temp & 1){
				tempCounter++;
}
temp = temp >> 1;

}
	if(tempCounter == k){
		counter++;
}

} 
std::cout << counter%(10000000000 + 7) << "\n";	
	return 0;
	
}