시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 6 6 85.714%

문제

백준이는 대학에서 ACM-ICPC를 함께 공부한 Sogang ACM-ICPC Team 회원들과 사진을 찍으려고 한다. 

회원들은 여러 줄로 나누어서 설 것이고, 앞 줄에 있는 사람의 수는 뒷 줄에 있는 사람의 수보다 작거나 같다. 그리고, 모든 줄은 왼쪽을 기준으로 정렬해서 줄을 설 것이다.

예를 들어 회원이 12명이라면, 뒤에서부터 앞까지 차례대로 5, 3, 3, 1명이 설 수 있다.

백준이는 모든 사람들이 사진에 나와야 한다고 생각한다. 따라서, 각 줄에 서있는 사람의 키는 왼쪽에서 오른쪽으로 갈 수록 작아져야 하고, 뒤에서 앞으로 올 수록 작아져야 한다.

12명의 학생이 있을 때, 5, 3, 3, 1과 같이 줄을 서는 2가지 경우는 다음과 같다. (1이 제일 키가 큰 사람)

학생의 수와 각 줄에 몇 명이 서야 하는 지가 주어졌을 때, 사진을 찍을 수 있는 서로 다른 대형의 수를 구하려고 한다.

학생이 6명이고, 3, 2, 1과 같이 줄을 서는 방법은 다음과 같이 16가지가 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 두 줄로 이루어져 있다. 첫째 줄에는 줄의 수 k가 주어진다. 둘째 줄에는 가장 뒷 줄부터 앞 줄까지 몇 명의 사람이 줄을 서야 하는지가 공백으로 구분되어 주어진다. (n1, n2, ..., nk)

k는 5보다 작거나 같은 자연수이고, 전체 학생의 수는 30보다 작거나 같다.

출력

각 테스트 케이스에 대해, 한 줄에 하나씩 사진 찍는 대형의 수를 출력한다. 이 값은 4294967295보다 작거나 같다.

예제 입력 1

6
1
30
5
1 1 1 1 1
3
3 2 1
4
5 3 3 1
5
6 5 4 3 2
2
15 15

예제 출력 1

1
1
16
4158
141892608
9694845

힌트

W3sicHJvYmxlbV9pZCI6IjI3NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWM5YzBcdWI5YzkgXHVjMGFjXHVjOWM0IFx1Y2MwZFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBBQ00tSUNQQ1x1Yjk3YyBcdWQ1NjhcdWFlZDggXHVhY2Y1XHViZDgwXHVkNTVjIFNvZ2FuZyBBQ00tSUNQQyBUZWFtIFx1ZDY4Y1x1YzZkMFx1YjRlNFx1YWNmYyBcdWMwYWNcdWM5YzRcdWM3NDQgXHVjYzBkXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVkNjhjXHVjNmQwXHViNGU0XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWM5MDRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1YzEyNCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzU1ZSBcdWM5MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWIyOTQgXHViNGI3IFx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NDAgXHVjNjdjXHVjYWJkXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NzRcdWMxMWMgXHVjOTA0XHVjNzQ0IFx1YzEyNCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVkNjhjXHVjNmQwXHVjNzc0IDEyXHViYTg1XHVjNzc0XHViNzdjXHViYTc0LCBcdWI0YTRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNTVlXHVhZTRjXHVjOWMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyA1LCAzLCAzLCAxXHViYTg1XHVjNzc0IFx1YzEyNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NjcmVlbiUyMFNob3QlMjAyMDEyLTExLTA2JTIwYXQlMjAlRUMlOTglQTQlRUMlQTAlODQlMjAyXzUyXzQ4LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjY5cHg7IHdpZHRoOjk5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjMGFjXHVjOWM0XHVjNWQwIFx1YjA5OFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjMTFjXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwYTRcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4XHViODVkIFx1Yzc5MVx1YzU0NFx1YzgzOFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YjRhNFx1YzVkMFx1YzExYyBcdWM1NWVcdWM3M2NcdWI4NWMgXHVjNjJjIFx1YzIxOFx1Yjg1ZCBcdWM3OTFcdWM1NDRcdWM4MzhcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xMlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgNSwgMywgMywgMVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOTA0XHVjNzQ0IFx1YzExY1x1YjI5NCAyXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiAoMVx1Yzc3NCBcdWM4MWNcdWM3N2MgXHVkMGE0XHVhYzAwIFx1ZDA3MCBcdWMwYWNcdWI3OGMpPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTEtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDJfNTJfNTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzVweDsgd2lkdGg6MjgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YmE4NyBcdWJhODVcdWM3NzQgXHVjMTFjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1Y2MwZFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMzAwXHVkNjE1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWM3NzQgNlx1YmE4NVx1Yzc3NFx1YWNlMCwgMywgMiwgMVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOTA0XHVjNzQ0IFx1YzExY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCAxNlx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTEtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDJfNTJfNTQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NThweDsgd2lkdGg6NTM1cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzkwNFx1Yzc1OCBcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjRiNyBcdWM5MDRcdWJkODBcdWQxMzAgXHVjNTVlIFx1YzkwNFx1YWU0Y1x1YzljMCBcdWJhODcgXHViYTg1XHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM5MDRcdWM3NDQgXHVjMTFjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKG4xLCBuMiwgLi4uLCBuayk8XC9wPlxyXG5cclxuPHA+a1x1YjI5NCA1XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHVhY2UwLCBcdWM4MDRcdWNjYjQgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YjI5NCAzMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMGFjXHVjOWM0IFx1Y2MwZFx1YjI5NCBcdWIzMDBcdWQ2MTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCA0Mjk0OTY3Mjk1XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1yLiBZb3VuZ1x1MjAxOXMgUGljdHVyZSBQZXJtdXRhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPk1yLiBZb3VuZyB3aXNoZXMgdG8gdGFrZSBhIHBpY3R1cmUgb2YgaGlzIGNsYXNzLiBUaGUgc3R1ZGVudHMgd2lsbCBzdGFuZCBpbiByb3dzIHdpdGggZWFjaCByb3cgbm8gbG9uZ2VyIHRoYW4gdGhlIHJvdyBiZWhpbmQgaXQgYW5kIHRoZSBsZWZ0IGVuZHMgb2YgdGhlIHJvd3MgYWxpZ25lZC4gRm9yIGluc3RhbmNlLCAxMiBzdHVkZW50cyBjb3VsZCBiZSBhcnJhbmdlZCBpbiByb3dzIChmcm9tIGJhY2sgdG8gZnJvbnQpIG9mIDUsIDMsIDMgYW5kIDEgc3R1ZGVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTEtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDJfNTJfNDgucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjlweDsgd2lkdGg6OTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiBhZGRpdGlvbiwgTXIuIFlvdW5nIHdhbnRzIHRoZSBzdHVkZW50cyBpbiBlYWNoIHJvdyBhcnJhbmdlZCBzbyB0aGF0IGhlaWdodHMgZGVjcmVhc2UgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBBbHNvLCBzdHVkZW50IGhlaWdodHMgc2hvdWxkIGRlY3JlYXNlIGZyb20gdGhlIGJhY2sgdG8gdGhlIGZyb250LiBUaGlua2luZyBhYm91dCBpdCwgTXIuIFlvdW5nIHNlZXMgdGhhdCBmb3IgdGhlIDEyLXN0dWRlbnQgZXhhbXBsZSwgdGhlcmUgYXJlIGF0IGxlYXN0IHR3byB3YXlzIHRvIGFycmFuZ2UgdGhlIHN0dWRlbnRzICh3aXRoIDEgYXMgdGhlIHRhbGxlc3QgZXRjLik6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTEtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDJfNTJfNTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzVweDsgd2lkdGg6MjgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TXIuIFlvdW5nIHdvbmRlcnMgaG93IG1hbnkgZGlmZmVyZW50IGFycmFuZ2VtZW50cyBvZiB0aGUgc3R1ZGVudHMgdGhlcmUgbWlnaHQgYmUgZm9yIGEgZ2l2ZW4gYXJyYW5nZW1lbnQgb2Ygcm93cy4gSGUgdHJpZXMgY291bnRpbmcgYnkgaGFuZCBzdGFydGluZyB3aXRoIHJvd3Mgb2YgMywgMiBhbmQgMSBhbmQgY291bnRzIDE2IGFycmFuZ2VtZW50czombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TY3JlZW4lMjBTaG90JTIwMjAxMi0xMS0wNiUyMGF0JTIwJUVDJTk4JUE0JUVDJUEwJTg0JTIwMl81Ml81NC5wbmdcIiBzdHlsZT1cImhlaWdodDo1OHB4OyB3aWR0aDo1MzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Nci4gWW91bmcgc2VlcyB0aGF0IGNvdW50aW5nIGJ5IGhhbmQgaXMgbm90IGdvaW5nIHRvIGJlIHZlcnkgZWZmZWN0aXZlIGZvciBhbnkgcmVhc29uYWJsZSBudW1iZXIgb2Ygc3R1ZGVudHMgc28gaGUgYXNrcyB5b3UgdG8gaGVscCBvdXQgYnkgd3JpdGluZyBhIGNvbXB1dGVyIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGFycmFuZ2VtZW50cyBvZiBzdHVkZW50cyBmb3IgYSBnaXZlbiBzZXQgb2Ygcm93cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlIHdpbGwgY29uc2lzdCBvZiB0d28gbGluZXMuIFRoZSBmaXJzdCBsaW5lIGdpdmVzIHRoZSBudW1iZXIgb2Ygcm93cywgaywgYXMgYSBkZWNpbWFsIGludGVnZXIuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgbGVuZ3RocyBvZiB0aGUgcm93cyBmcm9tIGJhY2sgdG8gZnJvbnQgKG4xLCBuMiwgJmhlbGxpcDssIG5rKSBhcyBkZWNpbWFsIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIHByb2JsZW0gc2V0IGVuZHMgd2l0aCBhIGxpbmUgd2l0aCBhIHJvdyBjb3VudCBvZiAwLiBUaGVyZSB3aWxsIG5ldmVyIGJlIG1vcmUgdGhhbiA1IHJvd3MgYW5kIHRoZSB0b3RhbCBudW1iZXIgb2Ygc3R1ZGVudHMsIE4sIChzdW0gb2YgdGhlIHJvdyBsZW5ndGhzKSB3aWxsIGJlIGF0IG1vc3QgMzAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlIHNoYWxsIGJlIHRoZSBudW1iZXIgb2YgYXJyYW5nZW1lbnRzIG9mIHRoZSBOIHN0dWRlbnRzIGludG8gdGhlIGdpdmVuIHJvd3Mgc28gdGhhdCB0aGUgaGVpZ2h0cyBkZWNyZWFzZSBhbG9uZyBlYWNoIHJvdyBmcm9tIGxlZnQgdG8gcmlnaHQgYW5kIGFsb25nIGVhY2ggY29sdW1uIGZyb20gYmFjayB0byBmcm9udCBhcyBhIGRlY2ltYWwgaW50ZWdlci4gKEFzc3VtZSBhbGwgaGVpZ2h0cyBhcmUgZGlzdGluY3QuKSBUaGUgcmVzdWx0IG9mIGVhY2ggcHJvYmxlbSBpbnN0YW5jZSBzaG91bGQgYmUgb24gYSBzZXBhcmF0ZSBsaW5lLiBUaGUgaW5wdXQgZGF0YSB3aWxsIGJlIGNob3NlbiBzbyB0aGF0IHRoZSByZXN1bHQgd2lsbCBhbHdheXMgZml0IGluIGFuIHVuc2lnbmVkIDMyIGJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2004 Greater New York Programming Contest I번