시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 47 26 23 54.762%

문제

해빈시의 공원에는 화장실이 두 개가 있다. 그런데 그 중 하나가 얼마전에 고장났다. 이제 남은 건 한 개 뿐이다....

문제는 해빈이는 당장 화장실이 가고 싶은데, 화장실 앞의 줄이 매우 길다는 것이다!

고통을 잊기 위해 해빈이는 절망적인 줄을 쳐다보며 아래와 같은 문제를 풀기 시작했다.

화장실 사용료는 50원이다. 줄에 서 있는 사람들 중 반은 50원 동전을 가지고 있고, 나머지 반은 100원 동전만 가지고 있다.

화장실을 개장할 때, 관리인은 거슬러 줄 동전을 가지고 있지 않다.

100원 동전만 가진 사람에게는 50원 동전을 거슬러 줘야 한다. (이 경우, 50원 동전을 가진 사람이 먼저 등어가면서 지불한 동전을 거스름돈으로 사용한다)

사람들의 위치를 적절히 바꿔서 관리인의 거스름돈이 항상 모자라지 않게 하는 방법의 수를 구하라. 이때, 일부 사람들은 절대로 자리를 바꾸지 않는다. (뒤쪽, 앞쪽 모두 다)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 길이가 n (1 ≤ n ≤ 1,000) 인 문자열 한 줄로 이루어져 있으며, 50원 동전을 가지고 있으면서 자리를 바꾸길 원치 않는 사람을 나타내는 '('와 100원 동전을 가지고 있으면서 자리를 바꾸길 원치 않는 사람을 나타내는 ')', 자리를 바꿔도 되는 사람을 나타내는 '.'으로 이루어져 있다.

'('와 ')'의 개수는 각각 n/2개 이하이고, n은 항상 짝수이다.

출력

각 테스트 케이스에 대해 문제의 조건을 지키며 자리를 바꿀 수 있는 방법의 수를 출력하라. 단, 문제의 답이 매우 커질 수 있으므로 마지막 여섯자리만 출력한다.

예제 입력 1

....
.(..
)...
.....)......................

예제 출력 1

2
1
0
68484
W3sicHJvYmxlbV9pZCI6IjkyNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDhcdWI5ZGRcdWM4MDFcdWM3NzggXHVjOTA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWJlNDhcdWMyZGNcdWM3NTggXHVhY2Y1XHVjNmQwXHVjNWQwXHViMjk0IFx1ZDY1NFx1YzdhNVx1YzJlNFx1Yzc3NCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YzViY1x1YjljOFx1YzgwNFx1YzVkMCBcdWFjZTBcdWM3YTVcdWIwYWNcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWIwYThcdWM3NDAgXHVhYzc0IFx1ZDU1YyBcdWFjMWMgXHViZmQwXHVjNzc0XHViMmU0Li4uLjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFx1YjJmOVx1YzdhNSBcdWQ2NTRcdWM3YTVcdWMyZTRcdWM3NzQgXHVhYzAwXHVhY2UwIFx1YzJmNlx1Yzc0MFx1YjM3MCwgXHVkNjU0XHVjN2E1XHVjMmU0IFx1YzU1ZVx1Yzc1OCBcdWM5MDRcdWM3NzQgXHViOWU0XHVjNmIwIFx1YWUzOFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1ZDFiNVx1Yzc0NCBcdWM3OGFcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWM4MDhcdWI5ZGRcdWM4MDFcdWM3NzggXHVjOTA0XHVjNzQ0IFx1Y2NkMFx1YjJlNFx1YmNmNFx1YmE3MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuPHA+XHVkNjU0XHVjN2E1XHVjMmU0IFx1YzBhY1x1YzZhOVx1YjhjY1x1YjI5NCA1MFx1YzZkMFx1Yzc3NFx1YjJlNC4gXHVjOTA0XHVjNWQwIFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0IFx1YzkxMSBcdWJjMThcdWM3NDAgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJjMThcdWM3NDAgMTAwXHVjNmQwIFx1YjNkOVx1YzgwNFx1YjljYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NTRcdWM3YTVcdWMyZTRcdWM3NDQgXHVhYzFjXHVjN2E1XHVkNTYwIFx1YjU0YywgXHVhZDAwXHViOWFjXHVjNzc4XHVjNzQwIFx1YWM3MFx1YzJhY1x1YjdlYyBcdWM5MDQgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD4xMDBcdWM2ZDAgXHViM2Q5XHVjODA0XHViOWNjIFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGNcdWIyOTQgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhY1x1YjdlYyBcdWM5MThcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjNzc0IFx1YWNiZFx1YzZiMCwgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYTNjXHVjODAwIFx1YjRmMVx1YzViNFx1YWMwMFx1YmE3NFx1YzExYyBcdWM5YzBcdWJkODhcdWQ1NWMgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhNFx1Yjk4NFx1YjNjOFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YmMxNFx1YWZkNFx1YzExYyBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NTggXHVhYzcwXHVjMmE0XHViOTg0XHViM2M4XHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWJhYThcdWM3OTBcdWI3N2NcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy4gXHVjNzc0XHViNTRjLCBcdWM3N2NcdWJkODAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YzgwOFx1YjMwMFx1Yjg1YyBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE0XHVhZmI4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gKFx1YjRhNFx1Y2FiZCwgXHVjNTVlXHVjYWJkIFx1YmFhOFx1YjQ1MCBcdWIyZTQpPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKSBcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWMgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YWUzOCBcdWM2ZDBcdWNlNTggXHVjNTRhXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTsoJiMzOTtcdWM2NDAgMTAwXHVjNmQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0XHVjMTFjIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWFlMzggXHVjNmQwXHVjZTU4IFx1YzU0YVx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7KSYjMzk7LCBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE0XHVhZmQ0XHViM2M0IFx1YjQxOFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7LiYjMzk7XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7KCYjMzk7XHVjNjQwICYjMzk7KSYjMzk7XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFjMDFcdWFjMDEgblwvMlx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NzRcdWFjZTAsIG5cdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzAgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLiZuYnNwO1x1YjJlOCwgXHViYjM4XHVjODFjXHVjNzU4IFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVlY1x1YzEyZlx1Yzc5MFx1YjlhY1x1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5Mjc4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnJ1c3RyYXRlZCBRdWV1ZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHRvaWxldCBpbiBGcmVkZHkmcnNxdW87cyBnYXJkZW4gaXMgYnJva2VuLCBzbyBoaXMgb25seSBjaGFuY2UgYXJlIHB1YmxpYyB0b2lsZXRzIG5lYXJieS4gT25lIGRheSwgdGhlcmUgaXMgYSBsb25nIHF1ZXVlIG9mIHBlb3BsZSBpbiBmcm9udCBvZiB0aGUgdG9pbGV0cy4gRnJlZGR5IGlzIGluIGEgYmlnIG5lZWQgYW5kIHNvIGhlIGRlc3BlcmF0ZWx5IHdhbnRzIHRoZSBxdWV1ZSB0byBiZSBzZXJ2ZWQgYXMgcXVpY2sgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPlRvIHVzZSB0aGUgdG9pbGV0cywgeW91IG5lZWQgdG8gcGF5IDUgY3Jvd25zLiBIYWxmIG9mIHRoZSBwZW9wbGUgaW4gdGhlIHF1ZXVlIGhhdmUgYSA1LWNyb3duIGNvaW4gYW5kIHRoZSBvdGhlciBoYWxmIG9ubHkgaGF2ZSBhIDEwLWNyb3duIGNvaW4uIEluaXRpYWxseSwgdGhlIHRvaWxldCBvcGVyYXRvciBoYXMgbm8gY29pbnMsIHRodXMsIHRoZSBwZW9wbGUgaW4gdGhlIHF1ZXVlIGhhdmUgdG8gcmVvcmdhbml6ZSBzbyB0aGF0IHdoZW5ldmVyIHNvbWVvbmUgd2FudHMgdG8gcGF5IHdpdGggYSAxMC1jcm93biBjb2luLCB0aGUgb3BlcmF0b3IgaGFzIGF0IGxlYXN0IG9uZSA1LWNyb3duIGNvaW4gYXZhaWxhYmxlIGZyb20gcHJldmlvdXMgY3VzdG9tZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgaXNzdWUgaXMgdGhhdCBzb21lIG9mIHRoZSBwZW9wbGUgaW4gdGhlIHF1ZXVlIGFyZSB1bndpbGxpbmcgdG8gZ2l2ZSB1cCB0aGVpciBzcG90LiBEZXRlcm1pbmUgaW4gaG93IG1hbnkgd2F5cyBjYW4gdGhlIHBlb3BsZSB3aWxsaW5nIHRvIGNoYW5nZSB0aGVpciBwb3NpdGlvbiByZWFycmFuZ2UgdGhlbXNlbHZlcyBpbiB0aGUgcXVldWUgc28gdGhhdCB0aGUgb3BlcmF0b3IgYWx3YXlzIGhhcyBjaGFuZ2UgYXZhaWxhYmxlLiBUaGUgcG9zaXRpb25zIG9mIHRob3NlIHVud2lsbGluZyBjYW5ub3QgY2hhbmdlICh0aGV5IGNhbm5vdCBiZSBtb3ZlZCB0byBhIGxhdGVyIGJ1dCBhbHNvIHRvIGFuIGVhcmxpZXIgc3BvdCBpbiB0aGUgcmVhcnJhbmdlZCBxdWV1ZSkuIEZ1cnRoZXJtb3JlLCBhbW9uZyB0aG9zZSB3aWxsaW5nIHRvIGNoYW5nZSB0aGUgcG9zaXRpb24sIHRoZSByZWxhdGl2ZSBvcmRlciBvZiB0aG9zZSB3aXRoIHRoZSBzYW1lIGNvaW4gbXVzdCBiZSBwcmVzZXJ2ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIGEgbm9uLWVtcHR5IHN0cmluZyBvZiBwYXJlbnRoZXNlcyBhbmQgZG90cyBvZiBsZW5ndGggbiAmbGU7IDEgMDAwLiBBIGRvdCBpbmRpY2F0ZXMgYSBwZXJzb24gd2lsbGluZyB0byBjaGFuZ2UgdGhlaXIgcG9zaXRpb24gaW4gdGhlIHF1ZXVlLCBhbiBvcGVuaW5nIHBhcmVudGhlc2lzIGluZGljYXRlcyBhIHBlcnNvbiB1bndpbGxpbmcgdG8gY2hhbmdlIHRoZSBwb3NpdGlvbiB3aG8gaGFzIGEgNS1jcm93biBjb2luLCBhbmQgYSBjbG9zaW5nIHBhcmVudGhlc2lzIGluZGljYXRlcyBhIHBlcnNvbiB1bndpbGxpbmcgdG8gY2hhbmdlIHRoZSBwb3NpdGlvbiB3aG8gaGFzIGEgMTAtY3Jvd24gY29pbi48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhhdCBuIGlzIGV2ZW4gYW5kIHRoYXQgdGhlIHN0cmluZyBjb250YWlucyBhdCBtb3N0IG5cLzIgb3BlbmluZyBwYXJlbnRoZXNlcyBhbmQgYXQgbW9zdCBuXC8yIGNsb3Npbmcgb25lcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGNvbXB1dGUgdGhlIG51bWJlciBvZiB3YXlzIHRoZSBxdWV1ZSBjYW4gYmUgcmVhcnJhbmdlZCBzbyB0aGF0IHRoZSBjb25kaXRpb25zIGRlc2NyaWJlZCBpbiB0aGUgc3RhdGVtZW50IG9mIHRoZSBwcm9ibGVtIGFyZSBzYXRpc1x1ZmIwMWVkLiBTaW5jZSB0aGlzIG51bWJlciBtYXkgYmUgdG9vIGxhcmdlLCB5b3UgYXJlIG9ubHkgcmVxdWlyZWQgdG8gcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyIGVxdWFsIHRvIHRoZSBsYXN0IDYgZGlnaXRzIChpbiB0aGUgZGVjaW1hbCByZXByZXNlbnRhdGlvbikgb2YgdGhlIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==