// author : Nguyễn Trọng Nguyễn - ITK22 NBK
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair <int, int>
#define fi first
#define sc second
const int maxn = 3000;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
int t, n, k;
char a[maxn + 5];
ll dp[maxn + 5][maxn / 2 + 5];
char s[6] = {'(', ')', '[', ']', '{', '}'};
ll rnk = 1;
stack <char> st;
void add (ll &a, ll b) {
a += b;
if (a >= mod) a -= mod;
}
void init () {
cin >> t >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
}
ll calc (int id = 0, int len = 0) {
if (len < 0 or len > k) return 0;
if (id == n) return len == 0;
if (dp[id][len] != -1) return dp[id][len];
ll res = 0;
int mx = t == 1 ? 2 : 6;
for (int i = 0; i < mx; i++) {
if (i & 1) {
if (len == 0 or st.top() != s[i - 1]) continue;
st.pop();
add(res, calc(id + 1, len - 1));
st.push(s[i - 1]);
}
else {
st.push(s[i]);
add(res, calc(id + 1, len + 1));
st.pop();
}
}
return dp[id][len] = res;
}
void getrank (int id = 0, int len = 0) {
if (id == n or len < 0 or len > k) return ;
int mx = t == 1 ? 2 : 6;
for (int i = 0; i < mx; i++) {
if (i & 1) {
if (len == 0 or st.top() != s[i - 1]) continue;
st.pop();
if (a[id] != s[i]) add(rnk, calc(id + 1, len - 1));
else {
getrank(id + 1, len - 1);
return ;
}
st.push(s[i - 1]);
}
else {
st.push(s[i]);
if (a[id] != s[i]) add(rnk, calc(id + 1, len + 1));
else {
getrank(id + 1, len + 1);
return ;
}
st.pop();
}
}
}
void process () {
memset(dp, -1, sizeof dp);
ll total = calc();
getrank();
cout << rnk;
}
signed main () {
cin.tie(0)->sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
#endif
init();
process();
return 0;
}
Ly8gYXV0aG9yIDogTmd1eeG7hW4gVHLhu41uZyBOZ3V54buFbiAtIElUSzIyIE5CSwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgaWkgcGFpciA8aW50LCBpbnQ+CiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKCmNvbnN0IGludCBtYXhuID0gMzAwMDsKY29uc3QgaW50IGluZiA9IChpbnQpMWU5Owpjb25zdCBpbnQgbW9kID0gKGludCkxZTkgKyA3OwoKaW50IHQsIG4sIGs7CmNoYXIgYVttYXhuICsgNV07CmxsIGRwW21heG4gKyA1XVttYXhuIC8gMiArIDVdOwoKY2hhciBzWzZdID0geycoJywgJyknLCAnWycsICddJywgJ3snLCAnfSd9OwpsbCBybmsgPSAxOwpzdGFjayA8Y2hhcj4gc3Q7Cgp2b2lkIGFkZCAobGwgJmEsIGxsIGIpIHsKCWEgKz0gYjsKCWlmIChhID49IG1vZCkgYSAtPSBtb2Q7Cn0KCnZvaWQgaW5pdCAoKSB7CgljaW4gPj4gdCA+PiBuID4+IGs7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQljaW4gPj4gYVtpXTsKfQoKbGwgY2FsYyAoaW50IGlkID0gMCwgaW50IGxlbiA9IDApIHsKCWlmIChsZW4gPCAwIG9yIGxlbiA+IGspIHJldHVybiAwOwoJaWYgKGlkID09IG4pIHJldHVybiBsZW4gPT0gMDsKCglpZiAoZHBbaWRdW2xlbl0gIT0gLTEpIHJldHVybiBkcFtpZF1bbGVuXTsKCglsbCByZXMgPSAwOwoJaW50IG14ID0gdCA9PSAxID8gMiA6IDY7Cglmb3IgKGludCBpID0gMDsgaSA8IG14OyBpKyspIHsKCQlpZiAoaSAmIDEpIHsKCQkJaWYgKGxlbiA9PSAwIG9yIHN0LnRvcCgpICE9IHNbaSAtIDFdKSBjb250aW51ZTsKCQkJc3QucG9wKCk7CgkJCWFkZChyZXMsIGNhbGMoaWQgKyAxLCBsZW4gLSAxKSk7CgkJCXN0LnB1c2goc1tpIC0gMV0pOwoJCX0KCQllbHNlIHsKCQkJc3QucHVzaChzW2ldKTsKCQkJYWRkKHJlcywgY2FsYyhpZCArIDEsIGxlbiArIDEpKTsKCQkJc3QucG9wKCk7CgkJfQoJfQoKCXJldHVybiBkcFtpZF1bbGVuXSA9IHJlczsKfQoKdm9pZCBnZXRyYW5rIChpbnQgaWQgPSAwLCBpbnQgbGVuID0gMCkgewoJaWYgKGlkID09IG4gb3IgbGVuIDwgMCBvciBsZW4gPiBrKSByZXR1cm4gOwoKCWludCBteCA9IHQgPT0gMSA/IDIgOiA2OwoJZm9yIChpbnQgaSA9IDA7IGkgPCBteDsgaSsrKSB7CgkJaWYgKGkgJiAxKSB7CgkJCWlmIChsZW4gPT0gMCBvciBzdC50b3AoKSAhPSBzW2kgLSAxXSkgY29udGludWU7CgkJCXN0LnBvcCgpOwoJCQlpZiAoYVtpZF0gIT0gc1tpXSkgYWRkKHJuaywgY2FsYyhpZCArIDEsIGxlbiAtIDEpKTsKCQkJZWxzZSB7CgkJCQlnZXRyYW5rKGlkICsgMSwgbGVuIC0gMSk7CgkJCQlyZXR1cm4gOwoJCQl9CgkJCXN0LnB1c2goc1tpIC0gMV0pOwoJCX0KCQllbHNlIHsKCQkJc3QucHVzaChzW2ldKTsKCQkJaWYgKGFbaWRdICE9IHNbaV0pIGFkZChybmssIGNhbGMoaWQgKyAxLCBsZW4gKyAxKSk7CgkJCWVsc2UgewoJCQkJZ2V0cmFuayhpZCArIDEsIGxlbiArIDEpOwoJCQkJcmV0dXJuIDsKCQkJfQoJCQlzdC5wb3AoKTsJCgkJfQoJfQp9Cgp2b2lkIHByb2Nlc3MgKCkgewoJbWVtc2V0KGRwLCAtMSwgc2l6ZW9mIGRwKTsKCWxsIHRvdGFsID0gY2FsYygpOwoJZ2V0cmFuaygpOwoJY291dCA8PCBybms7Cn0KCnNpZ25lZCBtYWluICgpIHsKCWNpbi50aWUoMCktPnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgkKCSNpZm5kZWYgT05MSU5FX0pVREdFCglmcmVvcGVuKCJ0ZXN0LmlucCIsInIiLHN0ZGluKTsKCWZyZW9wZW4oInRlc3Qub3V0IiwidyIsc3Rkb3V0KTsKCSNlbmRpZgoKCWluaXQoKTsKCXByb2Nlc3MoKTsKCglyZXR1cm4gMDsKfQ==