시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 23 17 47.222%

문제

올바른 괄호 문자열을 다음과 같이 정의한다.

  • ()와 []는 올바른 괄호 문자열이다.
  • A가 올바른 괄호 문자열이라면, (A)와 [A]도 올바른 괄호 문자열이다.
  • A와 B가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 AB도 올바른 괄호문자열이다.

적어도 한 쌍의 대괄호([와 그것에 대응하는 ])를 포함하고 있는 올바른 괄호 문자열이 있을 때, 모든 대괄호를 (로 바꾼 문자열을 부서진 괄호 문자열이라 한다.

예를 들어, ((와 ((((()))는 부서진 괄호 문자열이다. 첫 번째 문자열에서 올바른 괄호 문자열인 []를 얻을 수 있다. 두번째 문자열은 다음과 같은 4가지 올바른 괄호 문자열을 얻을 수 있다. []((())), ([](())), (([]())), ((([]))). 

부서진 괄호 문자열이 주어졌을 때, 여기서 얻을 수 있는 올바른 괄호 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 부서진 괄호 문자열의 길이 N(2≤N≤30000)이 주어진다. 둘째 줄에는 (와 )로 이루어진 길이가 N인 부서진 괄호 문자열이 주어진다.

출력

첫째 줄에 입력으로 주어진 부서진 괄호 문자열에서 얻을 수 있는 올바른 괄호 문자열의 개수를 1000000009로 나눈 나머지를 출력한다.

예제 입력 1

8
((((((((

예제 출력 1

14

힌트

예제의 경우에 얻을 수 있는 올바른 괄호 문자열은 다음과 같다.

[][][][], [[]][][], [[]][[]], [][][[]], [[[]]][], [[][]][], [][[][]], [][[[]]], [[[[]]]], [[][[]]], [[[]][]], [[][][]], [[[][]]], [][[]][]

W3sicHJvYmxlbV9pZCI6IjMzNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpXHVjNjQwIFtdXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCAoQSlcdWM2NDAgW0FdXHViM2M0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVjNjQwIEJcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3OCBBQlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjMzBkXHVjNzU4IFx1YjMwMFx1YWQwNFx1ZDYzOChbXHVjNjQwIFx1YWRmOFx1YWM4M1x1YzVkMCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgXSlcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViMzAwXHVhZDA0XHVkNjM4XHViOTdjIChcdWI4NWMgXHViYzE0XHVhZmJjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICgoXHVjNjQwICgoKCgoKSkpXHViMjk0IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OCBbXVx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIDRcdWFjMDBcdWM5YzAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFtdKCgoKSkpLCAoW10oKCkpKSwgKChbXSgpKSksICgoKFtdKSkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgTigyJmxlO04mbGU7MzAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAoXHVjNjQwIClcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEwMDAwMDAwMDlcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+W11bXVtdW10sIFtbXV1bXVtdLCBbW11dW1tdXSwgW11bXVtbXV0sIFtbW11dXVtdLCBbW11bXV1bXSwgW11bW11bXV0sIFtdW1tbXV1dLCBbW1tbXV1dXSwgW1tdW1tdXV0sIFtbW11dW11dLCBbW11bXVtdXSwgW1tbXVtdXV0sIFtdW1tdXVtdPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJhY2tldHMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCZyc3F1bztzIGRlZmluZSBhIGNvcnJlY3Qgc3RyaW5nIG9mIGJyYWNrZXRzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+KCkgYW5kIFtdIGFyZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM7PFwvbGk+XHJcblx0PGxpPmlmIEEgaXMgYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cywgdGhlbiAoQSkgYW5kIFtBXSBhcmUgYWxzbyBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM7PFwvbGk+XHJcblx0PGxpPmlmIEEgYW5kIEIgYXJlIGJvdGggY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzLCB0aGVuIHRoZSBjb25jYXRlbmF0aW9uIEFCIGlzIGFsc28gYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0czs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBhIGNvcnJlY3Qgc3RyaW5nIG9mIGJyYWNrZXRzIHdoaWNoIGNvbnRhaW5zIGF0IGxlYXN0IG9uZSBwYWlyIG9mIHNxdWFyZSBicmFja2V0czogWyBhbmQgY29ycmVzcG9uZGluZyBdLCBlYWNoIHNxdWFyZSBicmFja2V0IChib3RoIG9wZW5pbmcgYW5kIGNsb3NpbmcpIHdhcyByZXBsYWNlZCBieSB0aGUgb3BlbmluZyByb3VuZCBicmFja2V0LCB0aGVyZWZvcmUgb2J0YWluaW5nIGEgYnJva2VuIHN0cmluZyBvZiBicmFja2V0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsICgoIGFuZCAoKCgoKCkpKSBib3RoIGFyZSBicm9rZW4gc3RyaW5ncyBvZiBicmFja2V0cy4gRmlyc3Qgc3RyaW5nIGlzIG9idGFpbmVkIGZyb20gdGhlIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cyBbXS4gU2Vjb25kIHN0cmluZyBtYXkgYmUgb2J0YWluZWQgb25seSBmcm9tIHRoZSBmb2xsb3dpbmcgZm91ciBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM6IFtdKCgoKSkpLChbXSgoKSkpLCgoW10oKSkpIG9yICgoKFtdKSkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgZm9yIGEgZ2l2ZW4gYnJva2VuIHN0cmluZyBvZiBicmFja2V0cyBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHMgZnJvbSB3aGljaCB0aGUgZ2l2ZW4gYnJva2VuIHN0cmluZyBtYXkgaGF2ZSBiZWVuIG9idGFpbmVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGV4dCBmaWxlIGJyYWNrZXRzLmluIGNvbnRhaW5zIGEgc2luZ2xlIGV2ZW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDMwMDAwKSAtdGhlIGxlbmd0aCBvZiB0aGUgZ2l2ZW4gYnJva2VuIHN0cmluZyBvZiBicmFja2V0cy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gY2hhcmFjdGVycyAmbHNxdW87KCZyc3F1bzsgYW5kICZsc3F1bzspJnJzcXVvOyAtIHRoZSBnaXZlbiBicm9rZW4gc3RyaW5nIG9mIGJyYWNrZXRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBzaW5nbGUgbGluZSBvZiB0aGUgdGV4dCBmaWxlIGJyYWNrZXRzLm91dCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciAtIHRoZSByZXF1aXJlZCBudW1iZXIgb2YgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzLiBCZWNhdXNlIHRoZSBudW1iZXIgb2YgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzIGNhbiBiZSBsYXJnZSwgeW91IHNob3VsZCBvdXRwdXQgdGhlIGFuc3dlciBtb2R1bG8gMTAwMDAwMDAwOS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번