fq.cpp
#include <iostream>
#include <map>
typedef unsigned int uint;
std::map<std::string, uint> dp;
uint solve(const std::string& str) {
if (dp.count(str) == 0)
{
uint result = 0;
if (str[0] != ')')
for (uint close = 1; close < str.size(); close += 2)
{
if (str[close] == '(')
continue;
result += solve(str.substr(1, close - 1)) * solve(str.substr(close + 1, str.size() - close - 1));
result %= 1000000;
}
dp[str] = result;
}
return dp[str];
}
int main() {
dp[""] = 1;
dp[".."] = 1;
dp["()"] = 1;
dp["(."] = 1;
dp[".)"] = 1;
dp[")("] = 0;
dp[")."] = 0;
dp[".("] = 0;
while (true)
{
std::string line;
getline(std::cin, line);
if (std::cin.fail())
break;
uint result = solve(line);
std::cout << result << std::endl;
}
return 0;
}