求大佬看我口胡

//Per aspera ad astra.
//1004535809
#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>
#define re register
#define ll long long
using namespace std;
const int N = 5e2 + 5, P = 1e9 + 7;
int n, k; char str[N];
template<class T> T cmax(re T x, re T y) {return x > y ? x : y;}
template<class T> T cmin(re T x, re T y) {return x < y ? x : y;}
struct OI {
	int rp, score;
}CSPS2021;
struct id {
	int i, a, b, c, d;
};
map<id, int> f;
//i:浣嶇疆  a:褰撳墠瀛楃{*0,(1,)2}  b:鏄熷彿鏁伴噺  c:涓嶅皯0/缂哄彸鎷彿1  d:缂哄皯鐨勬暟閲?
inline bool operator < (re id x, re id y) {
	if (x.i ^ y.i) return x.i < y.i;
	if (x.a ^ y.a) return x.a < y.a;
	if (x.b ^ y.b) return x.b < y.b;
	if (x.c ^ y.c) return x.c < y.c;
	return x.d < y.d;
}
signed main() {
	++CSPS2021.rp, ++CSPS2021.score;
	freopen("bracket.in", "r", stdin);
	freopen("bracket.out", "w", stdout);
	scanf("%d%d%s", &n, &k, str + 1);
	if (str[1] != '?') {
		if (str[1] == '*') f[(id){1, 0, 1, 0, 0}] = 1;
		if (str[1] == '(') f[(id){1, 1, 0, 1, 1}] = 1;
		if (str[1] == ')')return !printf("0\n");
	}
	else f[(id){1, 0, 1, 0, 0}] = f[(id){1, 1, 0, 1, 1}] = 1;
	for (re int i = 2; i <= n; ++i)
		if (str[i] != '?') {
			if (str[i] == '*') {
				for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k - 1); ++a)
					for (re int b = 0; b < 2; ++b)
						for (re int c = 0; c <= (b ? n : 0); ++c)
							if (f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 0, a + 1, b, c}] = (f[(id){i, 0, a + 1, b, c}] + f[(id){i - 1, d, a, b, c}]) % P;
			}
			else if (str[i] == '(') {
				for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k); ++a)
					for (re int b = 0; b < 2; ++b)
						for(re int c = 0; c <= (b ? n : 0); ++c) {
							if (!b && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 1, 0, 1, 1}] = (f[(id){i, 1, 0, 1, 1}] + f[(id){i - 1, d, a, b, c}]) % P;
							else if (b == 1 && c < n && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 1, 0, 1, c + 1}] = (f[(id){i, 1, 0, 1, c + 1}] + f[(id){i - 1, d, a, b, c}]) % P;
						}
				
			}
			else if (str[i] == ')') {
				for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k); ++a)
					for (re int b = 0; b < 2; ++b)
						for (re int c = 0; c <= (b ? n : 0); ++c) {
							if (b == 1 && c > 0 && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 2, 0, b, c - 1}] = (f[(id){i, 2, 0, b, c - 1}] + f[(id){i - 1, d, a, b, c}]) % P;
							else if (b == 1 && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 2, 0, 0, 0}] = (f[(id){i, 2, 0, 0, 0}] + f[(id){i - 1, d, a, b, c}]) % P;
						}
			}
		}
		else if (str[i] == '?') {
			for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k - 1); ++a)
					for (re int b = 0; b < 2; ++b)
						for (re int c = 0; c <= (b ? n : 0); ++c)
							if (f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 0, a + 1, b, c}] = (f[(id){i, 0, a + 1, b, c}] + f[(id){i - 1, d, a, b, c}]) % P;
			for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k); ++a)
					for (re int b = 0; b < 2; ++b)
						for(re int c = 0; c <= (b ? n : 0); ++c) {
							if (!b && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 1, 0, 1, 1}] = (f[(id){i, 1, 0, 1, 1}] + f[(id){i - 1, d, a, b, c}]) % P;
							else if (b == 1 && c < n && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 1, 0, 1, c + 1}] = (f[(id){i, 1, 0, 1, c + 1}] + f[(id){i - 1, d, a, b, c}]) % P;
						}
			for (re int d = 0; d < 3; ++d)
				for (re int a = 0; a <= (d ? 0 : k); ++a)
					for (re int b = 0; b < 2; ++b)
						for (re int c = 0; c <= (b ? n : 0); ++c) {
							if (b == 1 && c > 0 && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 2, 0, b, c - 1}] = (f[(id){i, 2, 0, b, c - 1}] + f[(id){i - 1, d, a, b, c}]) % P;
							else if (b == 1 && f.count((id){i - 1, d, a, b, c}))
								f[(id){i, 2, 0, 0, 0}] = (f[(id){i, 2, 0, 0, 0}] + f[(id){i - 1, d, a, b, c}]) % P;
						}
		}
	/*for (re int i = 1; i <= n; ++i)
		for (re int d = 0; d < 3; ++d)
			for (re int a = 0; a <= k; ++a)
				for (re int b = 0; b < 2; ++b)
					for (re int c = 0; c <= n; ++c)
						if (f.count((id){i, d, a, b, c}))
							printf("%d %d %d %d %d: %d\n", i, d, a, b, c, f[(id){i, d, a, b, c}]);*/
	//map<id, int>::iterator it = f.begin();
	//for (; it != f.end(); ++it) printf("%d %d %d %d %d: %d\n", it->first.i, it->first.a, it->first.b, it->first.c, it->first.d, it->second); printf("\n");
	re int ans = 0;
	if (str[n] != '?') {
		re int d;
		if (str[n] == '*') d = 0;
		else if (str[n] == '(') d = 1;
		else if (str[n] == ')') d = 2;
		for (re int a = 0; a <= (d ? n : 0); ++a)
			if (f.count((id){n, d, a, 0, 0}))
				ans = (ans + f[(id){n, d, a, 0, 0}]) % P;
	}
	else
		for (re int d = 0; d < 3; ++d)
			for (re int a = 0; a <= (d ? n : 0); ++a)
				if (f.count((id){n, d, a, 0, 0}))
					ans = (ans + f[(id){n, d, a, 0, 0}]) % P;
	printf("%d\n", ans);
	return 392699 ^ 392699;
}