시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 102 40 29 39.189%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

8
((((((((

예제 출력 1

14

힌트

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

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

W3sicHJvYmxlbV9pZCI6IjMzNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpXHVjNjQwIFtdXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCAoQSlcdWM2NDAgW0FdXHViM2M0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVjNjQwIEJcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3OCBBQlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjMzBkXHVjNzU4IFx1YjMwMFx1YWQwNFx1ZDYzOChbXHVjNjQwIFx1YWRmOFx1YWM4M1x1YzVkMCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgXSlcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViMzAwXHVhZDA0XHVkNjM4XHViOTdjIChcdWI4NWMgXHViYzE0XHVhZmJjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICgoXHVjNjQwICgoKCgoKSkpXHViMjk0IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OCBbXVx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCA0XHVhYzAwXHVjOWMwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBbXSgoKCkpKSwgKFtdKCgpKSksICgoW10oKSkpLCAoKChbXSkpKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE4oMiZsZTtOJmxlOzMwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgKFx1YzY0MCApXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxMDAwMDAwMDA5XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPltdW11bXVtdLCBbW11dW11bXSwgW1tdXVtbXV0sIFtdW11bW11dLCBbW1tdXV1bXSwgW1tdW11dW10sIFtdW1tdW11dLCBbXVtbW11dXSwgW1tbW11dXV0sIFtbXVtbXV1dLCBbW1tdXVtdXSwgW1tdW11bXV0sIFtbW11bXV1dLCBbXVtbXV1bXTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJhY2tldHMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCZyc3F1bztzIGRlZmluZSBhIGNvcnJlY3Qgc3RyaW5nIG9mIGJyYWNrZXRzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+KCkgYW5kIFtdIGFyZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM7PFwvbGk+XHJcblx0PGxpPmlmIEEgaXMgYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cywgdGhlbiAoQSkgYW5kIFtBXSBhcmUgYWxzbyBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM7PFwvbGk+XHJcblx0PGxpPmlmIEEgYW5kIEIgYXJlIGJvdGggY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzLCB0aGVuIHRoZSBjb25jYXRlbmF0aW9uIEFCIGlzIGFsc28gYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0czs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBhIGNvcnJlY3Qgc3RyaW5nIG9mIGJyYWNrZXRzIHdoaWNoIGNvbnRhaW5zIGF0IGxlYXN0IG9uZSBwYWlyIG9mIHNxdWFyZSBicmFja2V0czogWyBhbmQgY29ycmVzcG9uZGluZyBdLCBlYWNoIHNxdWFyZSBicmFja2V0IChib3RoIG9wZW5pbmcgYW5kIGNsb3NpbmcpIHdhcyByZXBsYWNlZCBieSB0aGUgb3BlbmluZyByb3VuZCBicmFja2V0LCB0aGVyZWZvcmUgb2J0YWluaW5nIGEgYnJva2VuIHN0cmluZyBvZiBicmFja2V0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsICgoIGFuZCAoKCgoKCkpKSBib3RoIGFyZSBicm9rZW4gc3RyaW5ncyBvZiBicmFja2V0cy4gRmlyc3Qgc3RyaW5nIGlzIG9idGFpbmVkIGZyb20gdGhlIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cyBbXS4gU2Vjb25kIHN0cmluZyBtYXkgYmUgb2J0YWluZWQgb25seSBmcm9tIHRoZSBmb2xsb3dpbmcgZm91ciBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHM6IFtdKCgoKSkpLChbXSgoKSkpLCgoW10oKSkpIG9yICgoKFtdKSkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgZm9yIGEgZ2l2ZW4gYnJva2VuIHN0cmluZyBvZiBicmFja2V0cyBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHMgZnJvbSB3aGljaCB0aGUgZ2l2ZW4gYnJva2VuIHN0cmluZyBtYXkgaGF2ZSBiZWVuIG9idGFpbmVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgZXZlbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMzAwMDApIC10aGUgbGVuZ3RoIG9mIHRoZSBnaXZlbiBicm9rZW4gc3RyaW5nIG9mIGJyYWNrZXRzLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBjaGFyYWN0ZXJzICZsc3F1bzsoJnJzcXVvOyBhbmQgJmxzcXVvOykmcnNxdW87IC0gdGhlIGdpdmVuIGJyb2tlbiBzdHJpbmcgb2YgYnJhY2tldHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHNpbmdsZSBsaW5lIG9mIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciAtIHRoZSByZXF1aXJlZCBudW1iZXIgb2YgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzLiBCZWNhdXNlIHRoZSBudW1iZXIgb2YgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzIGNhbiBiZSBsYXJnZSwgeW91IHNob3VsZCBvdXRwdXQgdGhlIGFuc3dlciBtb2R1bG8gMTAwMDAwMDAwOS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번