#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  lighting.py
#  
#  Copyright 2018 Contest team 084 <cteam084@ostrava>
#  
#  This program is free software; you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation; either version 2 of the License, or
#  (at your option) any later version.
#  
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#  
#  You should have received a copy of the GNU General Public License
#  along with this program; if not, write to the Free Software
#  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#  MA 02110-1301, USA.
#  
#  

def poc(s):
	o = 0
	for i in s:
		if i is "1":
			o += 1
			
	return o

def reader():
	yield list(map(int, input().split()))
	yield input()
	raise StopIteration
	
def main():
	
	p, a = list(reader())
	N, K = p
	
	c=0
	aa = 0
	for i in reversed(a):
		if i is "1":
			aa += pow(2, c)
		c+=1
	a=aa
	
	z = pow(2, N )-1
	c = (a + 1)&z
	#print(N, K, bin(z), bin(a), poc(bin(c)[2:]))
	
	vysledek = 0
	
	for kolo in range(z+1):		
		if poc(bin((a + kolo))[2:]) is K:
			#print(bin(kolo))
			vysledek += 1

	print(vysledek)
	return 0

if __name__ == '__main__':
	main()