시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB194594330.935%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

4
((()

예제 출력 1

2

[](), ([])

예제 입력 2

8
((((((((

예제 출력 2

14

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

W3sicHJvYmxlbV9pZCI6IjMzNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPigpPFwvY29kZT5cdWM2NDAgPGNvZGU+W108XC9jb2RlPlx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+PGNvZGU+QTxcL2NvZGU+XHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCA8Y29kZT4oQSk8XC9jb2RlPlx1YzY0MCA8Y29kZT5bQV08XC9jb2RlPlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+PGNvZGU+QTxcL2NvZGU+XHVjNjQwIDxjb2RlPkI8XC9jb2RlPlx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM1YjQgXHViZDk5XHVjNzc4IDxjb2RlPkFCPFwvY29kZT5cdWIzYzQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YzMwZFx1Yzc1OCBcdWIzMDBcdWFkMDRcdWQ2MzgoPGNvZGU+WzxcL2NvZGU+XHVjNjQwIFx1YWRmOFx1YWM4M1x1YzVkMCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgPGNvZGU+XTxcL2NvZGU+KVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWIzMDBcdWFkMDRcdWQ2MzhcdWI5N2MgPGNvZGU+KDxcL2NvZGU+XHViODVjIFx1YmMxNFx1YWZiYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA8Y29kZT4oKDxcL2NvZGU+XHVjNjQwIDxjb2RlPigoKCgoKSkpPFwvY29kZT5cdWIyOTQgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc4IDxjb2RlPltdPFwvY29kZT5cdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgNFx1YWMwMFx1YzljMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gPGNvZGU+W10oKCgpKSk8XC9jb2RlPiwgPGNvZGU+KFtdKCgpKSk8XC9jb2RlPiwgPGNvZGU+KChbXSgpKSk8XC9jb2RlPiwgPGNvZGU+KCgoW10pKSk8XC9jb2RlPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE4oMiAmbGU7IE4gJmxlOyAzMDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDxjb2RlPig8XC9jb2RlPlx1YzY0MCA8Y29kZT4pPFwvY29kZT5cdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDlcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPjxjb2RlPltdKCk8XC9jb2RlPiwgPGNvZGU+KFtdKTxcL2NvZGU+PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPjxjb2RlPltdW11bXVtdPFwvY29kZT4sIDxjb2RlPltbXV1bXVtdPFwvY29kZT4sIDxjb2RlPltbXV1bW11dPFwvY29kZT4sIDxjb2RlPltdW11bW11dPFwvY29kZT4sIDxjb2RlPltbW11dXVtdPFwvY29kZT4sIDxjb2RlPltbXVtdXVtdPFwvY29kZT4sIDxjb2RlPltdW1tdW11dPFwvY29kZT4sIDxjb2RlPltdW1tbXV1dPFwvY29kZT4sIDxjb2RlPltbW1tdXV1dPFwvY29kZT4sIDxjb2RlPltbXVtbXV1dPFwvY29kZT4sIDxjb2RlPltbW11dW11dPFwvY29kZT4sIDxjb2RlPltbXVtdW11dPFwvY29kZT4sIDxjb2RlPltbW11bXV1dPFwvY29kZT4sIDxjb2RlPltdW1tdXVtdPFwvY29kZT48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMzQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJhY2tldHMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCZyc3F1bztzIGRlZmluZSBhIGNvcnJlY3Qgc3RyaW5nIG9mIGJyYWNrZXRzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+KCk8XC9jb2RlPiBhbmQgPGNvZGU+W108XC9jb2RlPiBhcmUgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzOzxcL2xpPlxyXG5cdDxsaT5pZiA8Y29kZT5BPFwvY29kZT4gaXMgYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cywgdGhlbiA8Y29kZT4oQSk8XC9jb2RlPiBhbmQgPGNvZGU+W0FdPFwvY29kZT4gYXJlIGFsc28gY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzOzxcL2xpPlxyXG5cdDxsaT5pZiA8Y29kZT5BPFwvY29kZT4gYW5kIDxjb2RlPkI8XC9jb2RlPiBhcmUgYm90aCBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHMsIHRoZW4gdGhlIGNvbmNhdGVuYXRpb24gPGNvZGU+QUI8XC9jb2RlPiBpcyBhbHNvIGEgY29ycmVjdCBzdHJpbmcgb2YgYnJhY2tldHM7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cyB3aGljaCBjb250YWlucyBhdCBsZWFzdCBvbmUgcGFpciBvZiBzcXVhcmUgYnJhY2tldHM6IDxjb2RlPls8XC9jb2RlPiBhbmQgY29ycmVzcG9uZGluZyA8Y29kZT5dPFwvY29kZT4sIGVhY2ggc3F1YXJlIGJyYWNrZXQgKGJvdGggb3BlbmluZyBhbmQgY2xvc2luZykgd2FzIHJlcGxhY2VkIGJ5IHRoZSBvcGVuaW5nIHJvdW5kIGJyYWNrZXQsIHRoZXJlZm9yZSBvYnRhaW5pbmcgYSBicm9rZW4gc3RyaW5nIG9mIGJyYWNrZXRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgPGNvZGU+KCg8XC9jb2RlPiBhbmQgPGNvZGU+KCgoKCgpKSk8XC9jb2RlPiBib3RoIGFyZSBicm9rZW4gc3RyaW5ncyBvZiBicmFja2V0cy4gRmlyc3Qgc3RyaW5nIGlzIG9idGFpbmVkIGZyb20gdGhlIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cyA8Y29kZT5bXTxcL2NvZGU+LiBTZWNvbmQgc3RyaW5nIG1heSBiZSBvYnRhaW5lZCBvbmx5IGZyb20gdGhlIGZvbGxvd2luZyBmb3VyIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0czogPGNvZGU+W10oKCgpKSk8XC9jb2RlPiwgPGNvZGU+KFtdKCgpKSk8XC9jb2RlPiwgPGNvZGU+KChbXSgpKSk8XC9jb2RlPiBvciA8Y29kZT4oKChbXSkpKTxcL2NvZGU+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgZm9yIGEgZ2l2ZW4gYnJva2VuIHN0cmluZyBvZiBicmFja2V0cyBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHMgZnJvbSB3aGljaCB0aGUgZ2l2ZW4gYnJva2VuIHN0cmluZyBtYXkgaGF2ZSBiZWVuIG9idGFpbmVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgZXZlbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMzAwMDApIC10aGUgbGVuZ3RoIG9mIHRoZSBnaXZlbiBicm9rZW4gc3RyaW5nIG9mIGJyYWNrZXRzLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBjaGFyYWN0ZXJzICZsc3F1bzs8Y29kZT4oPFwvY29kZT4mcnNxdW87IGFuZCAmbHNxdW87PGNvZGU+KTxcL2NvZGU+JnJzcXVvOyAtIHRoZSBnaXZlbiBicm9rZW4gc3RyaW5nIG9mIGJyYWNrZXRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBzaW5nbGUgbGluZSBvZiBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgLSB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cy4gQmVjYXVzZSB0aGUgbnVtYmVyIG9mIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cyBjYW4gYmUgbGFyZ2UsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSBhbnN3ZXIgbW9kdWxvIDEsMDAwLDAwMCwwMDkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD48Y29kZT5bXSgpPFwvY29kZT4sIDxjb2RlPihbXSk8XC9jb2RlPjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD48Y29kZT5bXVtdW11bXTxcL2NvZGU+LCA8Y29kZT5bW11dW11bXTxcL2NvZGU+LCA8Y29kZT5bW11dW1tdXTxcL2NvZGU+LCA8Y29kZT5bXVtdW1tdXTxcL2NvZGU+LCA8Y29kZT5bW1tdXV1bXTxcL2NvZGU+LCA8Y29kZT5bW11bXV1bXTxcL2NvZGU+LCA8Y29kZT5bXVtbXVtdXTxcL2NvZGU+LCA8Y29kZT5bXVtbW11dXTxcL2NvZGU+LCA8Y29kZT5bW1tbXV1dXTxcL2NvZGU+LCA8Y29kZT5bW11bW11dXTxcL2NvZGU+LCA8Y29kZT5bW1tdXVtdXTxcL2NvZGU+LCA8Y29kZT5bW11bXVtdXTxcL2NvZGU+LCA8Y29kZT5bW1tdW11dXTxcL2NvZGU+LCA8Y29kZT5bXVtbXV1bXTxcL2NvZGU+PFwvcD5cclxuIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번