#include <bits/stdc++.h>
using namespace std;
class BracketSequenceDiv1 {
public:
int n;
string s;
typedef long long LL;
LL memo[41][41][41][4];
LL f(int p, int Lr, int Ls, int last)
{
if (p == n)
return Lr == 0 && Ls == 0 && last != 3;
LL& res = memo[p][Lr][Ls][last];
if (res != -1LL)
return res;
res = 0;
if (s[p] == '(')
{
res = f(p+1, Lr+1, Ls, 0)+f(p+1, Lr, Ls, last);
}
else if (s[p] == '[')
{
res = f(p+1, Lr, Ls+1, 1)+f(p+1, Lr, Ls, last);
}
else if (s[p] == ')')
{
if (Lr == 0 && Ls == 0)
res = f(p+1, Lr, Ls, last);
else if (Lr > 0 && Ls == 0)
res = f(p+1, Lr, Ls, last)+f(p+1, Lr-1, Ls, Lr-1?0:2);
else if (Lr == 0 && Ls > 0)
res = f(p+1, Lr, Ls, last);
else // Lr > 0 && Ls > 0
{
res = f(p+1, Lr, Ls, last);
if (last != 1)
res += f(p+1, Lr-1, Ls, Lr-1?0:1);
}
}
else // s[p] == ']'
{
if (Lr == 0 && Ls == 0)
res = f(p+1, Lr, Ls, last);
else if (Lr > 0 && Ls == 0)
res = f(p+1, Lr, Ls, last);
else if (Lr == 0 && Ls > 0)
res = f(p+1, Lr, Ls, last)+f(p+1, Lr, Ls-1, Ls-1?1:2);
else
{
res = f(p+1, Lr, Ls, last);
if (last != 0)
res += f(p+1, Lr, Ls-1, Ls-1?1:0);
}
}
return res;
}
long long count(string s_)
{
s = s_;
n = s.size();
memset(memo, -1, sizeof(memo));
return f(0, 0, 0, 3);
}
};
<%:testing-code%>
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmNsYXNzIEJyYWNrZXRTZXF1ZW5jZURpdjEgewpwdWJsaWM6CmludCBuOwpzdHJpbmcgczsKdHlwZWRlZiBsb25nIGxvbmcgTEw7CkxMIG1lbW9bNDFdWzQxXVs0MV1bNF07CgpMTCBmKGludCBwLCBpbnQgTHIsIGludCBMcywgaW50IGxhc3QpCnsKCWlmIChwID09IG4pCgkJcmV0dXJuIExyID09IDAgJiYgTHMgPT0gMCAmJiBsYXN0ICE9IDM7CgkKCUxMJiByZXMgPSBtZW1vW3BdW0xyXVtMc11bbGFzdF07CglpZiAocmVzICE9IC0xTEwpCgkJcmV0dXJuIHJlczsKCXJlcyA9IDA7CglpZiAoc1twXSA9PSAnKCcpCgl7CgkJcmVzID0gZihwKzEsIExyKzEsIExzLCAwKStmKHArMSwgTHIsIExzLCBsYXN0KTsKCX0KCWVsc2UgaWYgKHNbcF0gPT0gJ1snKQoJewoJCXJlcyA9IGYocCsxLCBMciwgTHMrMSwgMSkrZihwKzEsIExyLCBMcywgbGFzdCk7Cgl9CgllbHNlIGlmIChzW3BdID09ICcpJykKCXsKCQlpZiAoTHIgPT0gMCAmJiBMcyA9PSAwKQoJCQlyZXMgPSBmKHArMSwgTHIsIExzLCBsYXN0KTsKCQllbHNlIGlmIChMciA+IDAgJiYgTHMgPT0gMCkKCQkJcmVzID0gZihwKzEsIExyLCBMcywgbGFzdCkrZihwKzEsIExyLTEsIExzLCBMci0xPzA6Mik7CgkJZWxzZSBpZiAoTHIgPT0gMCAmJiBMcyA+IDApCgkJCXJlcyA9IGYocCsxLCBMciwgTHMsIGxhc3QpOwoJCWVsc2UgLy8gTHIgPiAwICYmIExzID4gMAoJCXsKCQkJcmVzID0gZihwKzEsIExyLCBMcywgbGFzdCk7CgkJCWlmIChsYXN0ICE9IDEpCgkJCQlyZXMgKz0gZihwKzEsIExyLTEsIExzLCBMci0xPzA6MSk7CgkJfQoJfQoJZWxzZSAvLyBzW3BdID09ICddJwoJewoJCWlmIChMciA9PSAwICYmIExzID09IDApCgkJCXJlcyA9IGYocCsxLCBMciwgTHMsIGxhc3QpOwoJCWVsc2UgaWYgKExyID4gMCAmJiBMcyA9PSAwKQoJCQlyZXMgPSBmKHArMSwgTHIsIExzLCBsYXN0KTsKCQllbHNlIGlmIChMciA9PSAwICYmIExzID4gMCkKCQkJcmVzID0gZihwKzEsIExyLCBMcywgbGFzdCkrZihwKzEsIExyLCBMcy0xLCBMcy0xPzE6Mik7CgkJZWxzZQoJCXsKCQkJcmVzID0gZihwKzEsIExyLCBMcywgbGFzdCk7CgkJCWlmIChsYXN0ICE9IDApCgkJCQlyZXMgKz0gZihwKzEsIExyLCBMcy0xLCBMcy0xPzE6MCk7CgkJfQoJfQoJcmV0dXJuIHJlczsKfQoKbG9uZyBsb25nIGNvdW50KHN0cmluZyBzXykgCnsKCXMgPSBzXzsKCW4gPSBzLnNpemUoKTsJCgltZW1zZXQobWVtbywgLTEsIHNpemVvZihtZW1vKSk7CgkKCXJldHVybiBmKDAsIDAsIDAsIDMpOwp9Cn07CgoKPCU6dGVzdGluZy1jb2RlJT4KLy9Qb3dlcmVkIGJ5IEthd2lnaUVkaXQgMi4xLjQgKGJldGEpIG1vZGlmaWVkIGJ5IHBpdmFub2Yh