긴 케이크 나눠주기

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 ≤ T ≤ 10$
• $1 ≤ k ≤ n ≤ 1\\,000\\,000$