program shift
  implicit none
  integer(8), parameter :: p = 998244353
  character(300) :: s
  integer :: k, n, c(300) = 0, m = 0, i, j
  integer(8) :: ans = 0
  read(*,*) s, k
  n = len_trim(s)
  do i = 1, n
    if (s(i:i) == '0') m = m + 1
  end do
  if (m == 0 .or. m == n) then
    write(*,'(i0)') 0
    stop
  end if
  m = m + 1
  j = m
  do i = n, 1, -1
    if (s(i:i) == '0') then
      j = j - 1
    else
      c(j) = c(j) + 1
    end if
  end do
  call dfs(m, 0, 0)
  write(*,'(i0)') ans
contains
  recursive subroutine dfs(i, l, t)
    integer, intent(in) :: i, l, t
    integer :: j, u
    integer :: f(300)
    if (i == 1) then
      u = t + l
      if (u <= k) ans = ans + 1
      return
    end if
    do j = 0, c(i) + l
      u = t + max(j - c(i), 0)
      call dfs(i - 1, c(i) + l - j, u)
    end do
  end
end program shift