#include<stdio.h>

long long mocnina (long long x)
{
long long vys=1,j;
for (j=1;j<=x;j++) vys*=2;
return vys;
}

int main()
{
long long n,k,i,output=0,vysledok=0,cislo=0,maxcislo=0,suma;
char c;
scanf("%Li %Li",&n,&k);
for (i=0;i<=n;i++) {scanf("%c",&c);if (c=='1')  cislo+=mocnina(n-i);}
for (i=1;i<=n;i++) maxcislo+=mocnina(n-i);
for (i=0;i<=maxcislo;i++) 
{
suma=cislo+i;
while (suma>0)
{if (suma%2==1 ) vysledok++;
suma/=2;
}
if (vysledok==k) output++;
vysledok=0;

}
output%=(1000000007);
printf("%Li\n",output);
return 0;
}