조명

바이너리 카지노의 조명 시스템은 중앙 제어 콘솔에 연결된 매우 복잡하고 안전한 장치로 제어된다. 콘솔에서는 각 조명의 상태가 1비트의 정보로 저장된다(0은 해당 조명이 꺼져 있음, 1은 켜져 있음). 따라서 건물에 있는 모든 조명의 전체 상태는 이진수 a로 나타낼 수 있다.

권한이 없는 사람이 조작하는 것을 막기 위해 조명 시스템에는 조명을 제어하는 특별한 방법이 있다. 조명의 구성을 바꾸려면 이진수 b를 입력해야 하며, 이 수는 표준 정수 덧셈으로 원래 구성 a에 더해진다.

여러분은 특정 개수의 조명이 켜져 있기를 원하며, 성공할 가능성이 얼마나 되는지 궁금하다. 조건에 맞는 이진수는 모두 몇 개인가?

첫 번째 줄에는 두 정수 N과 K가 주어진다(1 ≤ N ≤ 1000, 0 ≤ K ≤ N). N은 a와 b의 비트 수이고, K는 켜져 있어야 하는 조명의 개수이다. 두 번째 줄에는 길이가 N인 이진 정수 a가 주어진다.

합 a + b에서 1로 설정된 비트가 정확히 K개인 서로 다른 음이 아닌 N비트 정수 b의 개수를 출력한다. 결과가 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.