긴 케이크 나눠주기

Albert는 길이가 $n$인 긴 케이크를 구웠다. 이 케이크는 $n$등분할 수 있도록 총 $n$개의 칸으로 미리 나뉘어 있고, 일부 칸에는 과일 토핑이 올라가 있다.

예를 들어 아래 그림은 $n = 8$인 케이크이고, $0$은 토핑이 없는 칸, $1$은 과일 토핑이 있는 칸을 나타낸다. 이를 정수 배열로 나타내면 $A = [0, 1, 1, 0, 0, 1, 1, 0]$이다. $A[i]$는 $i$번째 칸에 토핑이 있으면 $1$, 없으면 $0$이다.

Albert는 이 케이크를 정확히 $k-1$번 잘라 $k$개의 조각으로 나누려고 한다. 이때 다음 조건을 만족해야 한다.

• 조건 1: 각 케이크 조각에 포함된 토핑이 올라간 칸의 개수가 모두 같아야 한다.
• 조건 2: 버려지는 칸이나 조각이 생겨서는 안 된다.

예를 들어 $k = 2$인 경우 버려지는 칸이나 조각 없이 위 케이크를 자를 수 있는 방법은 총 $7$가지이다. 그중 조건 1을 만족하는 방법은 아래 세 가지다. 각 케이크 조각에는 토핑이 올라간 칸이 두 개씩 있다.

다른 예로, 아래 그림은 $n = 5$, $A = [0, 1, 0, 1, 0]$, $k = 2$인 경우 위 조건을 만족하면서 케이크를 자를 수 있는 두 가지 방법을 나타낸다.

입력으로 $n$, $k$, 토핑의 유무를 나타내는 배열 $A$가 주어졌을 때, 조건을 만족하며 케이크를 자를 수 있는 방법의 수를 구하라. 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 두 줄로 주어진다. 첫 줄에 $n$과 $k$가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$의 값이 공백 없이 길이 $n$인 문자열로 주어진다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 10$
• $1 \le k \le n \le 1\,000\,000$