Travelling Salesman and Special Numbers

The Travelling Salesman는 여행하는 데 많은 시간을 보내기 때문에 지루해지는 경향이 있다. 시간을 보내기 위해 그는 수에 연산을 수행하는 것을 좋아한다. 그러한 연산 중 하나는 양의 정수 x를 가져와 x의 이진 표현에서 1로 설정된 비트의 개수로 줄이는 것이다. 예를 들어 수 13에 대해 1310 = 11012가 성립하므로, 설정된 비트가 3개이고 13은 한 번의 연산으로 3으로 줄어든다.

그는 어떤 수를 1로 줄이는 데 필요한 최소 연산 횟수가 k이면 그 수를 특별하다고 부른다.

그는 n보다 크지 않은 특별한 수가 몇 개 존재하는지 알아내고 싶어 한다. Travelling Salesman가 곧 목적지에 도착하려 하니 그를 도와주자!

답이 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

첫 번째 줄에는 정수 n (1 ≤ n < 21000)가 주어진다.

두 번째 줄에는 정수 k (0 ≤ k ≤ 1000)가 주어진다.

n은 앞에 불필요한 영이 없는 이진 표현으로 주어진다는 점에 유의한다.

n보다 크지 않은 특별한 수의 개수를 109 + 7로 나눈 나머지인 하나의 정수를 출력한다.

첫 번째 예제에서 세 특별한 수는 3, 5, 6이다. 이들은 한 번의 연산으로 2로 줄어들고(3, 5, 6 각각에 설정된 비트가 두 개 있기 때문이다), 그다음 한 번의 연산으로 1로 줄어든다(2에는 설정된 비트가 하나뿐이기 때문이다).