import core.bitop;
import std.algorithm;
import std.array;
import std.conv;
import std.range;
import std.stdio;
import std.string;

immutable int mod = 10 ^^ 9 + 7;
immutable int limit = 1003;

void add (ref int a, int b)
{
	a = (a + b) % mod;
}

void main ()
{
	auto h = new int [limit];
	h[1] = 0;
	foreach (i; 2..limit)
	{
		h[i] = h[popcnt (i)] + 1;
	}

	string s;
	while ((s = readln.strip) != "")
	{
		auto k = readln.strip.to !(int);
		if (k == 0)
		{
			writeln (1);
			continue;
		}

		auto n = s.length.to !(int);
		auto f = new int [2] [] [] (n + 1, n + 1);
		f[0][0][0] = 1;
		foreach (i; 0..n)
		{
			int lim = (s[i] == '1');
			foreach (j; 0..i + 1)
			{
				foreach (prevLess; 0..2)
				{
					foreach (cur; 0..2)
					{
						if ((cur > lim) && !prevLess)
						{
							continue;
						}
						int nextLess = prevLess ||
						    (cur < lim);
						add (f[i + 1][j + cur]
						    [nextLess], f[i][j]
						    [prevLess]);
					}
				}
			}
		}
		add (f[n][1][1], mod - 1);

		int res = 0;
		foreach (j; 1..n + 1)
		{
			if (h[j] == k - 1)
			{
				add (res, f[n][j][0]);
				add (res, f[n][j][1]);
			}
		}
		writeln (res);
	}
}
