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;
}