시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 750 409 324 57.961%

문제

높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자.

위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다.

막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, l, r이 주어진다. (1 ≤ l, r ≤ n ≤ 20)

출력

각 테스트 케이스마다, 입력으로 주어진 값에 해당하는 배치의 수를 출력한다.

예제 입력 1

4
4 1 2
4 1 1
5 2 4
20 2 1

예제 출력 1

2
0
4
6402373705728000
W3sicHJvYmxlbV9pZCI6Ijg4OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzlcdWIzMDAgXHViYzMwXHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOTJcdWM3NzRcdWFjMDAgMSwgMiwgLi4uLCBuXHVjNzc4IFx1YjljOVx1YjMwMCBuXHVhYzFjXHVhYzAwIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI5YzlcdWIzMDBcdWI5N2MgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YzExYyBcdWJjZjRcdWJhNzQsIFx1ZDA3MCBcdWI5YzlcdWIzMDBcdWFjMDAgXHViNGE0XHVjNWQwXHVjNzg4XHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhYzAwXHViOWFjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCA0XHVhYzFjXHVjNzU4IFx1YjljOVx1YjMwMFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNDUwIFx1YmMzMFx1Y2U1OFx1Yjk3YyBcdWMwYjRcdWQzYjRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvaW1hZ2VzXC9wb2xlYXJyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1N3B4OyB3aWR0aDo0MTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHViNDUwIFx1YmMzMFx1Y2U1OFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YmQyNFx1Yzc0NCBcdWI1NGMgXHViOWM5XHViMzAwXHVhYzAwIFx1ZDU1YyBcdWFjMWMgXHViY2Y0XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWMxMWMgXHViZDI0XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWI5YzlcdWIzMDBcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWJjZjRcdWM3NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOVx1YjMwMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHViZDI0XHVjNzQ0IFx1YjU0YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCBsLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWMxMWMgXHViZDI0XHVjNzQ0IFx1YjU0YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCByXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMzBcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBuLCBsLCByXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBsLCByICZsZTsgbiAmbGU7IDIwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWMxMlx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzMwXHVjZTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODg5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvbGUgQXJyYW5nZW1lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBuIHBvbGVzIG9mIGhlaWdodCAxLCAyLCAuLi4gLCBuIGluIGEgcm93LiBJZiB5b3UgbG9vayBhdCB0aGVzZSBwb2xlcyBmcm9tIHRoZSBsZWZ0IHNpZGUgb3IgdGhlIHJpZ2h0IHNpZGUsIHNtYWxsZXIgcG9sZXMgYXJlIGhpZGRlbiBieSB0YWxsZXIgcG9sZXMuIEZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgdHdvIGFycmFuZ2VtZW50cyBvZiA0IHBvbGVzIGluIHRoZSBuZXh0IGZpZ3VyZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb2xlYXJyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1N3B4OyB3aWR0aDo0MTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBhcnJhbmdlbWVudCwgb25seSBvbmUgcG9sZSBjYW4gYmUgc2VlbiBmcm9tIHRoZSBsZWZ0LCBhbmQgdHdvIHBvbGVzIGNhbiBiZSBzZWVuIGZyb20gdGhlIHJpZ2h0LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBhcnJhbmdlbWVudHMgb2YgbiBwb2xlcyBzdWNoIHRoYXQgc2VlbiBmcm9tIHRoZSBsZWZ0IHlvdSBzZWUgbCBwb2xlcyBhbmQgc2VlbiBmcm9tIHRoZSByaWdodCB5b3Ugc2VlIHIgcG9sZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgbGluZSBjb250YWluaW5nIHRocmVlIGludGVnZXJzLCBuLCBsLCBhbmQgciAoMSAmbGU7IGwsciAmbGU7IG4gJmxlOyAyMCksIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBwb2xlcyBhbmQgKHJlc3AuIHIpIGlzIHRoZSBudW1iZXIgb2YgcG9sZXMgdGhhdCBjYW4gYmUgc2VlbiBmcm9tIHRoZSBsZWZ0KHJlc3AuIHJpZ2h0KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBhcnJhbmdlbWVudHMgb2YgcG9sZXMgZm9yIHRoZSB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2012 H번