시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD4xMDBcdWM2ZDAgXHViM2Q5XHVjODA0XHViOWNjIFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGNcdWIyOTQgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhY1x1YjdlYyBcdWM5MThcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjNzc0IFx1YWNiZFx1YzZiMCwgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYTNjXHVjODAwIFx1YjRmMVx1YzViNFx1YWMwMFx1YmE3NFx1YzExYyBcdWM5YzBcdWJkODhcdWQ1NWMgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWM3MFx1YzJhNFx1Yjk4NFx1YjNjOFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YmMxNFx1YWZkNFx1YzExYyBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NTggXHVhYzcwXHVjMmE0XHViOTg0XHViM2M4XHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWJhYThcdWM3OTBcdWI3N2NcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy4gXHVjNzc0XHViNTRjLCBcdWM3N2NcdWJkODAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YzgwOFx1YjMwMFx1Yjg1YyBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE0XHVhZmI4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gKFx1YjRhNFx1Y2FiZCwgXHVjNTVlXHVjYWJkIFx1YmFhOFx1YjQ1MCBcdWIyZTQpPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKSBcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgNTBcdWM2ZDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWMgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YWUzOCBcdWM2ZDBcdWNlNTggXHVjNTRhXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTsoJiMzOTtcdWM2NDAgMTAwXHVjNmQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0XHVjMTFjIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWFlMzggXHVjNmQwXHVjZTU4IFx1YzU0YVx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7KSYjMzk7LCBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE0XHVhZmQ0XHViM2M0IFx1YjQxOFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7LiYjMzk7XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7KCYjMzk7XHVjNjQwICYjMzk7KSYjMzk7XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFjMDFcdWFjMDEgblwvMlx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NzRcdWFjZTAsIG5cdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzAgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLiZuYnNwO1x1YjJlOCwgXHViYjM4XHVjODFjXHVjNzU4IFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVlY1x1YzEyZlx1Yzc5MFx1YjlhY1x1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTI3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZydXN0cmF0ZWQgUXVldWUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB0b2lsZXQgaW4gRnJlZGR5JnJzcXVvO3MgZ2FyZGVuIGlzIGJyb2tlbiwgc28gaGlzIG9ubHkgY2hhbmNlIGFyZSBwdWJsaWMgdG9pbGV0cyBuZWFyYnkuIE9uZSBkYXksIHRoZXJlIGlzIGEgbG9uZyBxdWV1ZSBvZiBwZW9wbGUgaW4gZnJvbnQgb2YgdGhlIHRvaWxldHMuIEZyZWRkeSBpcyBpbiBhIGJpZyBuZWVkIGFuZCBzbyBoZSBkZXNwZXJhdGVseSB3YW50cyB0aGUgcXVldWUgdG8gYmUgc2VydmVkIGFzIHF1aWNrIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5UbyB1c2UgdGhlIHRvaWxldHMsIHlvdSBuZWVkIHRvIHBheSA1IGNyb3ducy4gSGFsZiBvZiB0aGUgcGVvcGxlIGluIHRoZSBxdWV1ZSBoYXZlIGEgNS1jcm93biBjb2luIGFuZCB0aGUgb3RoZXIgaGFsZiBvbmx5IGhhdmUgYSAxMC1jcm93biBjb2luLiBJbml0aWFsbHksIHRoZSB0b2lsZXQgb3BlcmF0b3IgaGFzIG5vIGNvaW5zLCB0aHVzLCB0aGUgcGVvcGxlIGluIHRoZSBxdWV1ZSBoYXZlIHRvIHJlb3JnYW5pemUgc28gdGhhdCB3aGVuZXZlciBzb21lb25lIHdhbnRzIHRvIHBheSB3aXRoIGEgMTAtY3Jvd24gY29pbiwgdGhlIG9wZXJhdG9yIGhhcyBhdCBsZWFzdCBvbmUgNS1jcm93biBjb2luIGF2YWlsYWJsZSBmcm9tIHByZXZpb3VzIGN1c3RvbWVycy48XC9wPlxyXG5cclxuPHA+VGhlIGlzc3VlIGlzIHRoYXQgc29tZSBvZiB0aGUgcGVvcGxlIGluIHRoZSBxdWV1ZSBhcmUgdW53aWxsaW5nIHRvIGdpdmUgdXAgdGhlaXIgc3BvdC4gRGV0ZXJtaW5lIGluIGhvdyBtYW55IHdheXMgY2FuIHRoZSBwZW9wbGUgd2lsbGluZyB0byBjaGFuZ2UgdGhlaXIgcG9zaXRpb24gcmVhcnJhbmdlIHRoZW1zZWx2ZXMgaW4gdGhlIHF1ZXVlIHNvIHRoYXQgdGhlIG9wZXJhdG9yIGFsd2F5cyBoYXMgY2hhbmdlIGF2YWlsYWJsZS4gVGhlIHBvc2l0aW9ucyBvZiB0aG9zZSB1bndpbGxpbmcgY2Fubm90IGNoYW5nZSAodGhleSBjYW5ub3QgYmUgbW92ZWQgdG8gYSBsYXRlciBidXQgYWxzbyB0byBhbiBlYXJsaWVyIHNwb3QgaW4gdGhlIHJlYXJyYW5nZWQgcXVldWUpLiBGdXJ0aGVybW9yZSwgYW1vbmcgdGhvc2Ugd2lsbGluZyB0byBjaGFuZ2UgdGhlIHBvc2l0aW9uLCB0aGUgcmVsYXRpdmUgb3JkZXIgb2YgdGhvc2Ugd2l0aCB0aGUgc2FtZSBjb2luIG11c3QgYmUgcHJlc2VydmVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgcGFyZW50aGVzZXMgYW5kIGRvdHMgb2YgbGVuZ3RoIG4gJmxlOyAxIDAwMC4gQSBkb3QgaW5kaWNhdGVzIGEgcGVyc29uIHdpbGxpbmcgdG8gY2hhbmdlIHRoZWlyIHBvc2l0aW9uIGluIHRoZSBxdWV1ZSwgYW4gb3BlbmluZyBwYXJlbnRoZXNpcyBpbmRpY2F0ZXMgYSBwZXJzb24gdW53aWxsaW5nIHRvIGNoYW5nZSB0aGUgcG9zaXRpb24gd2hvIGhhcyBhIDUtY3Jvd24gY29pbiwgYW5kIGEgY2xvc2luZyBwYXJlbnRoZXNpcyBpbmRpY2F0ZXMgYSBwZXJzb24gdW53aWxsaW5nIHRvIGNoYW5nZSB0aGUgcG9zaXRpb24gd2hvIGhhcyBhIDEwLWNyb3duIGNvaW4uPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgbiBpcyBldmVuIGFuZCB0aGF0IHRoZSBzdHJpbmcgY29udGFpbnMgYXQgbW9zdCBuXC8yIG9wZW5pbmcgcGFyZW50aGVzZXMgYW5kIGF0IG1vc3QgblwvMiBjbG9zaW5nIG9uZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBjb21wdXRlIHRoZSBudW1iZXIgb2Ygd2F5cyB0aGUgcXVldWUgY2FuIGJlIHJlYXJyYW5nZWQgc28gdGhhdCB0aGUgY29uZGl0aW9ucyBkZXNjcmliZWQgaW4gdGhlIHN0YXRlbWVudCBvZiB0aGUgcHJvYmxlbSBhcmUgc2F0aXNcdWZiMDFlZC4gU2luY2UgdGhpcyBudW1iZXIgbWF5IGJlIHRvbyBsYXJnZSwgeW91IGFyZSBvbmx5IHJlcXVpcmVkIHRvIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBvbmUgaW50ZWdlciBlcXVhbCB0byB0aGUgbGFzdCA2IGRpZ2l0cyAoaW4gdGhlIGRlY2ltYWwgcmVwcmVzZW50YXRpb24pIG9mIHRoZSBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d