# Pusheen Contest 2023 #2
###### tags: `CLA K22`

## TEAMBUILDING
Chia một dãy nhị phân thành các nhóm gồm các kí tự liên tiếp sao cho mỗi kí tự thuộc 1 nhóm mỗi nhóm có chênh lệch kí tự `0` và `1` không quá $k$.

### Subtask 1: $1 \leq n \leq 20$

Quay lui

int count = 0;
void backtrack(int i) {
    if (i > n) {
        ++count;
        return;
    }
    int diff = 0;
    for(int j = i; j <= n; ++j) {
        diff += (s[j] == '0') ? -1 : 1;
        if (abs(diff) <= k) backtrack(j+1);
    }
}

### Subtask 3: $1 \leq n \leq 5000$

Quy hoạch động

Công thức truy hồi
$$
\begin{cases}
dp[1] = 1 \\
dp[i] = \sum_j dp[j-1] && \text{ nếu } j \leq i \text{ và abs(diff}(i, j)) \leq k
\end{cases}
$$

#include <bits/stdc++.h>
using namespace std;

int n, k;
string s;
const int N = 5005;
const int MOD = 1e9+7;
int dp[N];

void Input() {
	cin >> n >> k;
	cin >> s;
}

void add(int &a, int b) {
	a += b; if (a >= MOD) a -= MOD;
}

void Solve() {
	s = '#' + s;
	dp[0] = 1;
	for(int i = 1; i <= n; ++i)+ {
		int diff = 0;
		for(int j = i-1; j >= 0; --j) {
			diff += s[j+1] == '0' ? -1 : 1;
			if (abs(diff) <= k) add(dp[i], dp[j]);
		}
	}
	cout << dp[n];
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	Input(), Solve();
	return 0;
}