시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 60 26 20 42.553%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

8
((((((((

예제 출력 1

14

힌트

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

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

W3sicHJvYmxlbV9pZCI6IjMzNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpXHVjNjQwIFtdXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCAoQSlcdWM2NDAgW0FdXHViM2M0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVjNjQwIEJcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3OCBBQlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjMzBkXHVjNzU4IFx1YjMwMFx1YWQwNFx1ZDYzOChbXHVjNjQwIFx1YWRmOFx1YWM4M1x1YzVkMCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgXSlcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViMzAwXHVhZDA0XHVkNjM4XHViOTdjIChcdWI4NWMgXHViYzE0XHVhZmJjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICgoXHVjNjQwICgoKCgoKSkpXHViMjk0IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OCBbXVx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCA0XHVhYzAwXHVjOWMwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBbXSgoKCkpKSwgKFtdKCgpKSksICgoW10oKSkpLCAoKChbXSkpKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZDgwXHVjMTFjXHVjOWM0IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE4oMiZsZTtOJmxlOzMwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgKFx1YzY0MCApXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWJkODBcdWMxMWNcdWM5YzQgXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmQ4MFx1YzExY1x1YzljNCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxMDAwMDAwMDA5XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPltdW11bXVtdLCBbW11dW11bXSwgW1tdXVtbXV0sIFtdW11bW11dLCBbW1tdXV1bXSwgW1tdW11dW10sIFtdW1tdW11dLCBbXVtbW11dXSwgW1tbW11dXV0sIFtbXVtbXV1dLCBbW1tdXVtdXSwgW1tdW11bXV0sIFtbW11bXV1dLCBbXVtbXV1bXTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJyYWNrZXRzIiwiZGVzY3JpcHRpb24iOiI8cD5MZXQmcnNxdW87cyBkZWZpbmUgYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpIGFuZCBbXSBhcmUgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzOzxcL2xpPlxyXG5cdDxsaT5pZiBBIGlzIGEgY29ycmVjdCBzdHJpbmcgb2YgYnJhY2tldHMsIHRoZW4gKEEpIGFuZCBbQV0gYXJlIGFsc28gY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzOzxcL2xpPlxyXG5cdDxsaT5pZiBBIGFuZCBCIGFyZSBib3RoIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cywgdGhlbiB0aGUgY29uY2F0ZW5hdGlvbiBBQiBpcyBhbHNvIGEgY29ycmVjdCBzdHJpbmcgb2YgYnJhY2tldHM7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gYSBjb3JyZWN0IHN0cmluZyBvZiBicmFja2V0cyB3aGljaCBjb250YWlucyBhdCBsZWFzdCBvbmUgcGFpciBvZiBzcXVhcmUgYnJhY2tldHM6IFsgYW5kIGNvcnJlc3BvbmRpbmcgXSwgZWFjaCBzcXVhcmUgYnJhY2tldCAoYm90aCBvcGVuaW5nIGFuZCBjbG9zaW5nKSB3YXMgcmVwbGFjZWQgYnkgdGhlIG9wZW5pbmcgcm91bmQgYnJhY2tldCwgdGhlcmVmb3JlIG9idGFpbmluZyBhIGJyb2tlbiBzdHJpbmcgb2YgYnJhY2tldHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCAoKCBhbmQgKCgoKCgpKSkgYm90aCBhcmUgYnJva2VuIHN0cmluZ3Mgb2YgYnJhY2tldHMuIEZpcnN0IHN0cmluZyBpcyBvYnRhaW5lZCBmcm9tIHRoZSBjb3JyZWN0IHN0cmluZ3Mgb2YgYnJhY2tldHMgW10uIFNlY29uZCBzdHJpbmcgbWF5IGJlIG9idGFpbmVkIG9ubHkgZnJvbSB0aGUgZm9sbG93aW5nIGZvdXIgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzOiBbXSgoKCkpKSwoW10oKCkpKSwoKFtdKCkpKSBvciAoKChbXSkpKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIGZvciBhIGdpdmVuIGJyb2tlbiBzdHJpbmcgb2YgYnJhY2tldHMgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgcG9zc2libGUgY29ycmVjdCBzdHJpbmdzIG9mIGJyYWNrZXRzIGZyb20gd2hpY2ggdGhlIGdpdmVuIGJyb2tlbiBzdHJpbmcgbWF5IGhhdmUgYmVlbiBvYnRhaW5lZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRleHQgZmlsZSBicmFja2V0cy5pbiBjb250YWlucyBhIHNpbmdsZSBldmVuIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAzMDAwMCkgLXRoZSBsZW5ndGggb2YgdGhlIGdpdmVuIGJyb2tlbiBzdHJpbmcgb2YgYnJhY2tldHMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGNoYXJhY3RlcnMgJmxzcXVvOygmcnNxdW87IGFuZCAmbHNxdW87KSZyc3F1bzsgLSB0aGUgZ2l2ZW4gYnJva2VuIHN0cmluZyBvZiBicmFja2V0cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgc2luZ2xlIGxpbmUgb2YgdGhlIHRleHQgZmlsZSBicmFja2V0cy5vdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgLSB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cy4gQmVjYXVzZSB0aGUgbnVtYmVyIG9mIGNvcnJlY3Qgc3RyaW5ncyBvZiBicmFja2V0cyBjYW4gYmUgbGFyZ2UsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSBhbnN3ZXIgbW9kdWxvIDEwMDAwMDAwMDkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번