fq.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int Way[2000][2000];
char Input[2000];
 
int main()
{
	while(fgets(Input, 2000, stdin))
	{
		memset(Way, 0, sizeof(Way));
		Way[0][0] = 1;
 
		int n = strlen(Input) - 1; //newline!
		//puts(Input);
 
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j <= i + 1; j++)
			{
				if(Input[i] != ')')
				{
					if(j)
					{
						Way[i + 1][j] += Way[i][j - 1];
						Way[i + 1][j] %= 1000000;
 
						/*if(Way[i][j - 1])
						{
							printf("A\n");
						}*/
					}
				}
 
				if(Input[i] != '(')
				{
					Way[i + 1][j] += Way[i][j + 1];
					Way[i + 1][j] %= 1000000;
				}
			}
		}
 
		printf("%d\n", Way[n][0]);
	}
 
	return 0;
}