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

문제

한국 최고의 자물쇠 회사 마선영은 도어락을 생산한다. 이 도어락은 B(1 ≤ B ≤ 11)개의 버튼으로 이루어졌으며 각 버튼은 '1'부터 'B'까지 이름 붙여 있다. 도어락은 버튼 조합으로 이뤄진 비밀번호를 올바른 순서로 누른 후 손잡이를 돌리면 마법처럼-_- 열린다

버튼 조합은 한 개 이상의 버튼을 동시에 누르는 것이다. 비밀번호는 최소 한 개 이상의 이러한 버튼 조합들로 이뤄져 있다. 어떤 버튼을 한 조합에서 사용하면, 다른 조합에서는 사용할 수 없다. 아래는 B=8인 예이다.

(1-2-3)(4)(7-8)

위는 (1-2-3), (4), (7-8)의 조합 세 개로 이뤄진 올바른 비밀번호이다. 버튼 5와 6은 이 비밀번호에 사용하지 않았다.

(1-2-3)(2-4)(5-6)

위는 버튼 2가 조합 (1-2-3)과 (2-4)에 두 번 나왔기 때문에 올바른 비밀번호가 아니다.

마선영의 CEO인 김선영은 정선영에게 B개의 버튼이 있을 때, 가능한 비밀번호의 수를 구하는 프로그램을 작성해 달라고 부탁했다. 프로그램은 고객의 도어락 리스트를 받아 주문 번호와 B값, 가능한 비밀번호 수를 출력해야 한다. 도어락 리스트는 최소 한 개, 최대 백 개의 도어락을 포함하고 있다.

정선영이 만들어야 하는 프로그램을 우리가 대신 만들어보자.

입력

첫 줄은 도어락 개수인 정수 N(1 ≤ N ≤ 100)이 주어진다. 다음 줄부터 N개의 도어락 버튼의 개수 B가 주어진다.

출력

각각의 도어락마다 가능한 비밀번호의 개수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
3
4
3

예제 출력 1

25
149
25

힌트

W3sicHJvYmxlbV9pZCI6IjI3MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyMGNcdWI3ZWNcdWMxMWMgXHVjN2EwXHVhZTA4IFx1ZDU3NFx1YzgxYyIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdFx1ZDU1Y1x1YWQ2ZCBcdWNkNWNcdWFjZTBcdWM3NTggXHVjNzkwXHViYjNjXHVjMWUwIFx1ZDY4Y1x1YzBhYyBcdWI5YzhcdWMxMjBcdWM2MDFcdWM3NDAgXHViM2M0XHVjNWI0XHViNzdkXHVjNzQ0IFx1YzBkZFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjNjNFx1YzViNFx1Yjc3ZFx1Yzc0MCBCKDEgJmxlOyBCICZsZTsgMTEpXHVhYzFjXHVjNzU4IFx1YmM4NFx1ZDJiY1x1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4NGNcdWM3M2NcdWJhNzAgXHVhYzAxIFx1YmM4NFx1ZDJiY1x1Yzc0MCAmIzM5OzEmIzM5O1x1YmQ4MFx1ZDEzMCAmIzM5O0ImIzM5O1x1YWU0Y1x1YzljMCBcdWM3NzRcdWI5ODQgXHViZDk5XHVjNWVjIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjNWI0XHViNzdkXHVjNzQwIFx1YmM4NFx1ZDJiYyBcdWM4NzBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTA0XHVjOWM0IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM2MmNcdWJjMTRcdWI5NzggXHVjMjFjXHVjMTFjXHViODVjIFx1YjIwNFx1Yjk3OCBcdWQ2YzQgXHVjMTkwXHVjN2ExXHVjNzc0XHViOTdjIFx1YjNjY1x1YjlhY1x1YmE3NCBcdWI5YzhcdWJjOTVcdWNjOThcdWI3ZmMtXy0gXHVjNWY0XHViOWIwXHViMmU0PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmM4NFx1ZDJiYyBcdWM4NzBcdWQ1NjlcdWM3NDAgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWIyMDRcdWI5NzRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJjODRcdWQyYmMgXHVjODcwXHVkNTY5XHViNGU0XHViODVjIFx1Yzc3NFx1YjkwNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWJjODRcdWQyYmNcdWM3NDQgXHVkNTVjIFx1Yzg3MFx1ZDU2OVx1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YjJlNFx1Yjk3OCBcdWM4NzBcdWQ1NjlcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YzU0NFx1Yjc5OFx1YjI5NCBCPThcdWM3NzggXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQoMS0yLTMpKDQpKDctOCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHViMjk0ICgxLTItMyksICg0KSwgKDctOClcdWM3NTggXHVjODcwXHVkNTY5IFx1YzEzOCBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOTA0XHVjOWM0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuIFx1YmM4NFx1ZDJiYyA1XHVjNjQwIDZcdWM3NDAgXHVjNzc0IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQoMS0yLTMpKDItNCkoNS02KTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3MDRcdWIyOTQgXHViYzg0XHVkMmJjIDJcdWFjMDAgXHVjODcwXHVkNTY5ICgxLTItMylcdWFjZmMgKDItNClcdWM1ZDAgXHViNDUwIFx1YmM4OCBcdWIwOThcdWM2NTRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5YzhcdWMxMjBcdWM2MDFcdWM3NTggQ0VPXHVjNzc4IFx1YWU0MFx1YzEyMFx1YzYwMVx1Yzc0MCBcdWM4MTVcdWMxMjBcdWM2MDFcdWM1ZDBcdWFjOGMgQlx1YWMxY1x1Yzc1OCBcdWJjODRcdWQyYmNcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NzQgXHViMmVjXHViNzdjXHVhY2UwIFx1YmQ4MFx1ZDBjMVx1ZDU4OFx1YjJlNC4gXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YWNlMFx1YWMxZFx1Yzc1OCBcdWIzYzRcdWM1YjRcdWI3N2QgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YmMxYlx1YzU0NCBcdWM4ZmNcdWJiMzggXHViYzg4XHVkNjM4XHVjNjQwIEJcdWFjMTIsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1YzViNFx1Yjc3ZCBcdWI5YWNcdWMyYTRcdWQyYjhcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDU1YyBcdWFjMWMsIFx1Y2Q1Y1x1YjMwMCBcdWJjMzEgXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzViNFx1Yjc3ZFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWMxMjBcdWM2MDFcdWM3NzQgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNmIwXHViOWFjXHVhYzAwIFx1YjMwMFx1YzJlMCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWIgXHVjOTA0XHVjNzQwIFx1YjNjNFx1YzViNFx1Yjc3ZCBcdWFjMWNcdWMyMThcdWM3NzggXHVjODE1XHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzViNFx1Yjc3ZCBcdWJjODRcdWQyYmNcdWM3NTggXHVhYzFjXHVjMjE4IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzYzRcdWM1YjRcdWI3N2RcdWI5YzhcdWIyZTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQdXNoIEJ1dHRvbiBMb2NrIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgRnJvYm96eiBNYWdpYyBMb2NrIENvbXBhbnkgaXMgaW4gdGhlIGJ1c2luZXNzIG9mIG1hbnVmYWN0dXJpbmcgcHVzaCBidXR0b25zdHlsZSBjb21iaW5hdGlvbiBkb29yIGxvY2tzLiBBIHB1c2ggYnV0dG9uIGRvb3IgbG9jayBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBwdXNoIGJ1dHRvbnMgQiwgKDEgJmxlOyBCICZsZTsgMTEpLCBsYWJlbGVkICZsZHF1bzsxJnJkcXVvOyB0aHJvdWdoICZsZHF1bztCJnJkcXVvOy4gVGhlIGxvY2sgaXMgb3BlbmVkIGJ5IHByZXNzaW5nIHRoZSBjb3JyZWN0IHNlcXVlbmNlIG9mIGJ1dHRvbiBjb21iaW5hdGlvbnMgYW5kIHRoZW4gdHVybmluZyB0aGUgZG9vcmtub2IuIElmIHRoZSBzZXF1ZW5jZSBvZiBwcmVzc2VzIGlzIGNvcnJlY3QsIHRoZSBkb29yIG1hZ2ljYWxseSBvcGVucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBjb21iaW5hdGlvbiBjb25zaXN0cyBvZiAxIG9yIG1vcmUgYnV0dG9ucyBiZWluZyBwcmVzc2VkIHNpbXVsdGFuZW91c2x5LiBBIHNlcXVlbmNlIGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIGNvbWJpbmF0aW9ucy4gQSBzZXF1ZW5jZSBtdXN0IGhhdmUgYXQgbGVhc3Qgb25lIGNvbWJpbmF0aW9uLiBPbmNlIGEgYnV0dG9uIGhhcyBiZWVuIHVzZWQgaW4gYSBjb21iaW5hdGlvbiwgaXQgbWF5IG5vdCBiZSB1c2VkIGFnYWluIGluIHRoZSBzYW1lIHNlcXVlbmNlLiBJbiBhZGRpdGlvbiwgaXQgaXMgbm90IG5lY2Vzc2FyeSB0byB1c2UgYWxsIHRoZSBidXR0b25zIGluIGEgc2VxdWVuY2UuIEZvciBleGFtcGxlLCBmb3IgQj04OiZuYnNwOzxcL3A+XHJcblxyXG48cD4oMS0yLTMpKDQpKDctOCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+aXMgYSB2YWxpZCBzZXF1ZW5jZSB3aXRoIDMgY29tYmluYXRpb25zICgxLTItMyksICg0KSwgYW5kICg3LTgpLiBOb3RlIHRoYXQgYnV0dG9ucyA1IGFuZCA2IGFyZSBub3QgdXNlZCBpbiB0aGlzIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4oMS0yLTMpKDItNCkoNS02KSZuYnNwOzxcL3A+XHJcblxyXG48cD5pcyBub3QgYSB2YWxpZCBzZXF1ZW5jZSwgc2luY2UgYnV0dG9uIDIgYXBwZWFycyBpbiAyIGNvbWJpbmF0aW9ucyAoMS0yLTMpIGFuZCAoMi00KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIENFTyBvZiBGcm9ib3p6LCBKLiBQaWVycG9udCBGbGF0aGVhZCwgd2FudHMgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG51bWJlciBvZiB2YWxpZCBzZXF1ZW5jZXMgcG9zc2libGUgZm9yIGdpdmVuIHZhbHVlcyBvZiBCLiBUaGUgcHJvZ3JhbSBtdXN0IGJlIGFibGUgdG8gcHJvY2VzcyBhIGxpc3Qgb2YgbG9jayBvcmRlcnMgKGRhdGFzZXRzKSBmcm9tIGN1c3RvbWVycyBhbmQgZ2VuZXJhdGUgYSByZXBvcnQgc2hvd2luZyB0aGUgb3JkZXIgbnVtYmVyLCB0aGUgdmFsdWUgb2YgQiwgYW5kIHRoZSBudW1iZXIgb2YgdmFsaWQgc2VxdWVuY2VzIHBvc3NpYmxlLiBUaGlzIGxpc3Qgd2lsbCBhbHdheXMgY29udGFpbiBhdCBsZWFzdCBvbmUgZGF0YXNldCwgYnV0IG5vIG1vcmUgdGhhbiAxMDAgZGF0YXNldHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4sICgxICZsZTsgTiAmbGU7IDEwMCksIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGRhdGFzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGFzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBvZiBkYXRhIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBCLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGJ1dHRvbnMgZm9yIHRoZSBsb2NrLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIGRpc3BsYXkgdGhlIGRhdGFzZXQgbnVtYmVyLCBhIGJsYW5rLCB0aGUgdmFsdWUgQiwgYSBibGFuaywgYW5kIHRoZSBudW1iZXIgb2YgdmFsaWQgc2VxdWVuY2VzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==