시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 23 18 51.429%

문제

올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키파를 도와 올바른 괄호쌍이 되도록 고쳐 주자.

키파는 괄호를 입력할 때 매우 조심했기 때문에 한 번만 오타를 내었다. 올바른 괄호쌍은 다음과 같이 정의된다:

  • ()는 올바른 괄호쌍이다.
  • A가 올바른 괄호쌍이라면 (A) 또한 올바른 괄호쌍이다.
  • A와 B가 올바른 괄호쌍이라면 AB 또한 올바른 괄호쌍이다.

입력

첫째 줄에 키파가 입력한 괄호열이 주어진다. 길이는 1 이상 100,000 이하이다.

출력

첫째 줄에 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력한다.

예제 입력 1

()(())))

예제 출력 1

4

힌트

키파가 입력한 다음 문자열을 자세히 보자:

12345678
()(())))

2번째 문자 )를 (로 고침으로써 올바른 문자열을 만들 수 있다:

12345678
(((())))

비슷하게, 5번째 문자, 6번째 문자, 혹은 7번째 문자를 고침으로써 올바른 문자열을 만들 수 있다.

W3sicHJvYmxlbV9pZCI6IjU4NzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWQwYzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDBhNFx1ZDMwY1x1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgXHViMTc4XHVkMmI4XHViZDgxXHVjNzQ0IFx1YzBjMFx1YjJlNC4mbmJzcDtcdWFkZjhcdWI3ZjBcdWIzNzAmbmJzcDtcdWQwYTRcdWJjZjRcdWI0ZGNcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjEwOFx1YmIzNCBcdWM3OTFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQwYTRcdWQzMGNcdWIyOTQgXHVkNjM5XHVjMmRjJm5ic3A7XHVjNWVjXHViMjk0IFx1YWQwNFx1ZDYzOFx1YzY0MCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWM3OThcdWJhYmIgXHVjNzg1XHViODI1XHVkNTU4XHVjOWMwJm5ic3A7XHVjNTRhXHVjNTU4XHViMjk0XHVjOWMwIFx1YWM3MVx1YzgxNVx1YjQxOFx1YzVjOFx1YjJlNC4mbmJzcDtcdWQwYTRcdWQzMGNcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzYyY1x1YmMxNFx1Yjk3OCZuYnNwO1x1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQmbmJzcDtcdWFjZTBcdWNjZDAgXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWQwYTRcdWQzMGNcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU2MCBcdWI1NGMgXHViOWU0XHVjNmIwIFx1Yzg3MFx1YzJlY1x1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNTVjIFx1YmM4OFx1YjljYyZuYnNwO1x1YzYyNFx1ZDBjMFx1Yjk3YyBcdWIwYjRcdWM1YzhcdWIyZTQuIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+KClcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHVjMzBkXHVjNzc0XHViNzdjXHViYTc0IChBKSBcdWI2MTBcdWQ1NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YzY0MCBCXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NzRcdWI3N2NcdWJhNzQgQUIgXHViNjEwXHVkNTVjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGE0XHVkMzBjXHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWFkMDRcdWQ2MzhcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFlMzhcdWM3NzRcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMTAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM3NTggXHViYjM4XHVjNzkwXHViOWNjIFx1YWNlMFx1Y2NkMFx1YzExYyZuYnNwO1x1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NzQgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiI8cD5cdWQwYTRcdWQzMGNcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzkwXHVjMTM4XHVkNzg4IFx1YmNmNFx1Yzc5MDo8XC9wPlxyXG5cclxuPHByZT5cclxuMTIzNDU2NzhcclxuKCkoKCkpKSk8XC9wcmU+XHJcblxyXG48cD4yXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MCApXHViOTdjIChcdWI4NWMgXHVhY2UwXHVjZTY4XHVjNzNjXHViODVjXHVjMzY4IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjEyMzQ1Njc4XHJcbigoKCgpKSkpPFwvcHJlPlxyXG5cclxuPHA+XHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjLCA1XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MCwgNlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAsIFx1ZDYzOVx1Yzc0MCA3XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWFjZTBcdWNlNjhcdWM3M2NcdWI4NWNcdWMzNjggXHVjNjJjXHViYzE0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU4NzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUeXBvIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgaGFzIGp1c3QgcHVyY2hhc2VkIGEgbmV3IGxhcHRvcCBjb21wdXRlciwgYnV0IHNoZSB1bmZvcnR1bmF0ZWx5IGZpbmRzIGhlcnNlbGYgdW5hYmxlIHRvIHR5cGUgd2VsbCwgZ2l2ZW4gdGhlIHNpemUgb2YgaGVyIGxhcmdlIGhvb3ZlcyByZWxhdGl2ZSB0byB0aGUgc21hbGwga2V5Ym9hcmQuIEJlc3NpZSBoYXMganVzdCBhdHRlbXB0ZWQgdG8gdHlwZSBpbiBvbmUgb2YgaGVyIGZhdm9yaXRlIHBhdHRlcm5zIC0tIGEgYmFsYW5jZWQgc3RyaW5nIG9mIHBhcmVudGhlc2VzLiBIb3dldmVyLCBzaGUgcmVhbGl6ZXMgdGhhdCBzaGUgbWlnaHQgaGF2ZSBtaXMtdHlwZWQgb25lIGNoYXJhY3RlciwgYWNjaWRlbnRhbGx5IHJlcGxhY2luZyAoIHdpdGggKSBvciB2aWNlIHZlcnNhLiBQbGVhc2UgaGVscCBCZXNzaWUgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGxvY2F0aW9ucyBpbiB0aGUgc3RyaW5nIHN1Y2ggdGhhdCByZXZlcnNpbmcgdGhlIHNpbmdsZSBwYXJlbnRoZXNpcyBhdCB0aGF0IGxvY2F0aW9uIHdvdWxkIGNhdXNlIHRoZSBlbnRpcmUgc3RyaW5nIHRvIGJlY29tZSBiYWxhbmNlZC48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIHNldmVyYWwgd2F5cyB0byBkZWZpbmUgd2hhdCBpdCBtZWFucyBmb3IgYSBzdHJpbmcgb2YgcGFyZW50aGVzZXMgdG8gYmUgJnF1b3Q7YmFsYW5jZWQmcXVvdDsuIFBlcmhhcHMgdGhlIHNpbXBsZXN0IGRlZmluaXRpb24gaXMgdGhhdCB0aGVyZSBtdXN0IGJlIHRoZSBzYW1lIHRvdGFsIG51bWJlciBvZiAoJiMzOTtzIGFuZCApJiMzOTtzLCBhbmQgZm9yIGFueSBwcmVmaXggb2YgdGhlIHN0cmluZywgdGhlcmUgbXVzdCBiZSBhdCBsZWFzdCBhcyBtYW55ICgmIzM5O3MgYXMgKSYjMzk7cy4gRm9yIGV4YW1wbGUsIHRoZSBmb2xsb3dpbmcgc3RyaW5ncyBhcmUgYWxsIGJhbGFuY2VkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpPFwvbGk+XHJcblx0PGxpPigoKSk8XC9saT5cclxuXHQ8bGk+KCkoKCkoKSk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD53aGlsZSB0aGVzZSBhcmUgbm90OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPikoPFwvbGk+XHJcblx0PGxpPigpKSg8XC9saT5cclxuXHQ8bGk+KCgoKSkpKTxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzdHJpbmcgb2YgcGFyZW50aGVzZXMgb2YgbGVuZ3RoIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAsMDAwKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbnVtYmVyIG9mIHBvc2l0aW9ucyB3aXRoaW4gdGhlIGlucHV0IHN0cmluZyAoaWYgYW55KSBzdWNoIHRoYXQgcmV2ZXJzaW5nIHRoZSBwYXJlbnRoZXNpcyBhdCB0aGF0IHNpbmdsZSBwb3NpdGlvbiB3b3VsZCBjYXVzZSB0aGUgZW50aXJlIHN0cmluZyB0byBiZWNvbWUgYmFsYW5jZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPGg0Pk91dHB1dCBEZXRhaWxzPFwvaDQ+XHJcblxyXG48cD5JZiB3ZSBsb29rIGF0IHRoZSBpbnB1dCBzdHJpbmcgY2xvc2VseTo8XC9wPlxyXG5cclxuPHByZT4xMjM0NTY3OCBcclxuKCkoKCkpKSk8XC9wcmU+XHJcblxyXG48cD53ZSBmaW5kIHRoYXQgcmV2ZXJzaW5nIHRoZSBkaXJlY3Rpb24gb2YgdGhlIHBhcmVudGhlc2lzIGF0IHBvc2l0aW9uIDIgcmVzdWx0cyBpbiBhIGJhbGFuY2VkIHN0cmluZzo8XC9wPlxyXG5cclxuPHByZT4xMjM0NTY3OCBcclxuKCgoKCkpKSk8XC9wcmU+XHJcblxyXG48cD5TaW1pbGFybHksIHJldmVyc2luZyB0aGUgcGFyZW50aGVzaXMgYXQgcG9zaXRpb24gNSwgYXQgcG9zaXRpb24gNiwgb3IgYXQgcG9zaXRpb24gNywgYWxzbyByZXN1bHRzIGluIGEgYmFsYW5jZWQgc3RyaW5nLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d