시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 60 37 21 63.636%

문제

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

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

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

화장실 사용료는 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+XHJcblxyXG48cD4xMDBcdWM2ZDAgXHViM2Q5XHVjODA0XHViOWNjIFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGNcdWIyOTQgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhY1x1YjdlYyBcdWM5MThcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjNzc0IFx1YWNiZFx1YzZiMCwgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYTNjXHVjODAwIFx1YjRmMVx1YzViNFx1YWMwMFx1YmE3NFx1YzExYyBcdWM5YzBcdWJkODhcdWQ1NWMgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhNFx1Yjk4NFx1YjNjOFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YmMxNFx1YWZkNFx1YzExYyBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NTggXHVhYzcwXHVjMmE0XHViOTg0XHViM2M4XHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWJhYThcdWM3OTBcdWI3N2NcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy4gXHVjNzc0IFx1YjU0YywgXHVjNzdjXHViZDgwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWM4MDhcdWIzMDBcdWI4NWMgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIChcdWI0YTRcdWNhYmQsIFx1YzU1ZVx1Y2FiZCBcdWJhYThcdWI0NTAgXHViMmU0KTxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgbiAoMSAmbGU7IG4gJmxlOyAxLDAwMCkgXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIDUwXHVjNmQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0XHVjMTFjIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWFlMzggXHVjNmQwXHVjZTU4IFx1YzU0YVx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7KCYjMzk7XHVjNjQwIDEwMFx1YzZkMCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NFx1YzExYyBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE0XHVhZmI4XHVhZTM4IFx1YzZkMFx1Y2U1OCBcdWM1NGFcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAmIzM5OykmIzM5OywgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZkNFx1YjNjNCBcdWI0MThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAmIzM5Oy4mIzM5O1x1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4mIzM5OygmIzM5O1x1YzY0MCAmIzM5OykmIzM5O1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVhYzAxXHVhYzAxIG5cLzJcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzc0XHVhY2UwLCBuXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTcwIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4mbmJzcDtcdWIyZTgsIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1YjljOFx1YzljMFx1YjljOSBcdWM1ZWNcdWMxMmZcdWM3OTBcdWI5YWNcdWI5Y2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGcnVzdHJhdGVkIFF1ZXVlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgdG9pbGV0IGluIEZyZWRkeSZyc3F1bztzIGdhcmRlbiBpcyBicm9rZW4sIHNvIGhpcyBvbmx5IGNoYW5jZSBhcmUgcHVibGljIHRvaWxldHMgbmVhcmJ5LiBPbmUgZGF5LCB0aGVyZSBpcyBhIGxvbmcgcXVldWUgb2YgcGVvcGxlIGluIGZyb250IG9mIHRoZSB0b2lsZXRzLiBGcmVkZHkgaXMgaW4gYSBiaWcgbmVlZCBhbmQgc28gaGUgZGVzcGVyYXRlbHkgd2FudHMgdGhlIHF1ZXVlIHRvIGJlIHNlcnZlZCBhcyBxdWljayBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+VG8gdXNlIHRoZSB0b2lsZXRzLCB5b3UgbmVlZCB0byBwYXkgNSBjcm93bnMuIEhhbGYgb2YgdGhlIHBlb3BsZSBpbiB0aGUgcXVldWUgaGF2ZSBhIDUtY3Jvd24gY29pbiBhbmQgdGhlIG90aGVyIGhhbGYgb25seSBoYXZlIGEgMTAtY3Jvd24gY29pbi4gSW5pdGlhbGx5LCB0aGUgdG9pbGV0IG9wZXJhdG9yIGhhcyBubyBjb2lucywgdGh1cywgdGhlIHBlb3BsZSBpbiB0aGUgcXVldWUgaGF2ZSB0byByZW9yZ2FuaXplIHNvIHRoYXQgd2hlbmV2ZXIgc29tZW9uZSB3YW50cyB0byBwYXkgd2l0aCBhIDEwLWNyb3duIGNvaW4sIHRoZSBvcGVyYXRvciBoYXMgYXQgbGVhc3Qgb25lIDUtY3Jvd24gY29pbiBhdmFpbGFibGUgZnJvbSBwcmV2aW91cyBjdXN0b21lcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBpc3N1ZSBpcyB0aGF0IHNvbWUgb2YgdGhlIHBlb3BsZSBpbiB0aGUgcXVldWUgYXJlIHVud2lsbGluZyB0byBnaXZlIHVwIHRoZWlyIHNwb3QuIERldGVybWluZSBpbiBob3cgbWFueSB3YXlzIGNhbiB0aGUgcGVvcGxlIHdpbGxpbmcgdG8gY2hhbmdlIHRoZWlyIHBvc2l0aW9uIHJlYXJyYW5nZSB0aGVtc2VsdmVzIGluIHRoZSBxdWV1ZSBzbyB0aGF0IHRoZSBvcGVyYXRvciBhbHdheXMgaGFzIGNoYW5nZSBhdmFpbGFibGUuIFRoZSBwb3NpdGlvbnMgb2YgdGhvc2UgdW53aWxsaW5nIGNhbm5vdCBjaGFuZ2UgKHRoZXkgY2Fubm90IGJlIG1vdmVkIHRvIGEgbGF0ZXIgYnV0IGFsc28gdG8gYW4gZWFybGllciBzcG90IGluIHRoZSByZWFycmFuZ2VkIHF1ZXVlKS4gRnVydGhlcm1vcmUsIGFtb25nIHRob3NlIHdpbGxpbmcgdG8gY2hhbmdlIHRoZSBwb3NpdGlvbiwgdGhlIHJlbGF0aXZlIG9yZGVyIG9mIHRob3NlIHdpdGggdGhlIHNhbWUgY29pbiBtdXN0IGJlIHByZXNlcnZlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBub24tZW1wdHkgc3RyaW5nIG9mIHBhcmVudGhlc2VzIGFuZCBkb3RzIG9mIGxlbmd0aCBuICZsZTsgMSAwMDAuIEEgZG90IGluZGljYXRlcyBhIHBlcnNvbiB3aWxsaW5nIHRvIGNoYW5nZSB0aGVpciBwb3NpdGlvbiBpbiB0aGUgcXVldWUsIGFuIG9wZW5pbmcgcGFyZW50aGVzaXMgaW5kaWNhdGVzIGEgcGVyc29uIHVud2lsbGluZyB0byBjaGFuZ2UgdGhlIHBvc2l0aW9uIHdobyBoYXMgYSA1LWNyb3duIGNvaW4sIGFuZCBhIGNsb3NpbmcgcGFyZW50aGVzaXMgaW5kaWNhdGVzIGEgcGVyc29uIHVud2lsbGluZyB0byBjaGFuZ2UgdGhlIHBvc2l0aW9uIHdobyBoYXMgYSAxMC1jcm93biBjb2luLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IG4gaXMgZXZlbiBhbmQgdGhhdCB0aGUgc3RyaW5nIGNvbnRhaW5zIGF0IG1vc3QgblwvMiBvcGVuaW5nIHBhcmVudGhlc2VzIGFuZCBhdCBtb3N0IG5cLzIgY2xvc2luZyBvbmVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIHdheXMgdGhlIHF1ZXVlIGNhbiBiZSByZWFycmFuZ2VkIHNvIHRoYXQgdGhlIGNvbmRpdGlvbnMgZGVzY3JpYmVkIGluIHRoZSBzdGF0ZW1lbnQgb2YgdGhlIHByb2JsZW0gYXJlIHNhdGlzXHVmYjAxZWQuIFNpbmNlIHRoaXMgbnVtYmVyIG1heSBiZSB0b28gbGFyZ2UsIHlvdSBhcmUgb25seSByZXF1aXJlZCB0byBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgb25lIGludGVnZXIgZXF1YWwgdG8gdGhlIGxhc3QgNiBkaWdpdHMgKGluIHRoZSBkZWNpbWFsIHJlcHJlc2VudGF0aW9uKSBvZiB0aGUgbnVtYmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==