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

문제

상근이는 학교 사물함에 매우 비싼 물건을 보관한다. 이렇게 중요한 물건을 학교에 보관하는 이유와 무엇이 그렇게 중요한지는 아직 알려지지 않았다. 하지만, 상근이는 보안을 유지하기 위해서 비밀번호가 9자리인 자물쇠를 이용한다.

이 자물쇠에는 LED 디스플레이가 있다. 상근이가 자물쇠를 만지면 자물쇠는 디스플레이에 숫자 하나를 보여준다. 이 숫자를 N이라고 했을 때, 다음과 같은 조건을 만족하는 트리의 개수의 마지막 9자리를 입력하면 자물쇠는 열린다.

노드가 N개있는 이진 트리가 있다. 이 때, 각 노드의 오른쪽 서브트리와 왼쪽 서브트리의 높이의 차이는 1이내이다. 서브트리의 높이란 그 서브트리의 루트와 리프 노드와의 경로의 길이 중에서 가장 긴 값이다. 노드가 하나있는 서브트리의 높이는 0이고, 노드가 없는 서브트리의 높이는 -1이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 정수 하나 N으로 이루어져 있다. N은 1보다 크거나 같고, 1427보다 작거나 같은 자연수이다.

출력

입력으로 주어진 N에 해당하는 트리의 개수의 마지막 9자리를 출력한다. (0을 출력해서 9자리로 맞춰야 한다)

예제 입력 1

1
3
6
21

예제 출력 1

000000001
000000001
000000004
000036900
W3sicHJvYmxlbV9pZCI6IjQ0NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNzkwXHViYjNjXHVjMWUwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTU5XHVhZDUwIFx1YzBhY1x1YmIzY1x1ZDU2OFx1YzVkMCBcdWI5ZTRcdWM2YjAgXHViZTQ0XHVjMmZjIFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWJjZjRcdWFkMDBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViYjNjXHVhYzc0XHVjNzQ0IFx1ZDU1OVx1YWQ1MFx1YzVkMCBcdWJjZjRcdWFkMDBcdWQ1NThcdWIyOTQgXHVjNzc0XHVjNzIwXHVjNjQwIFx1YmIzNFx1YzVjN1x1Yzc3NCBcdWFkZjhcdWI4MDdcdWFjOGMgXHVjOTExXHVjNjk0XHVkNTVjXHVjOWMwXHViMjk0IFx1YzU0NFx1YzljMSBcdWM1NGNcdWI4MjRcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjZjRcdWM1NDhcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWFjMDAgOVx1Yzc5MFx1YjlhY1x1Yzc3OCBcdWM3OTBcdWJiM2NcdWMxZTBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHVjNzkwXHViYjNjXHVjMWUwXHVjNWQwXHViMjk0IExFRCBcdWI1MTRcdWMyYTRcdWQ1MGNcdWI4MDhcdWM3NzRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzkwXHViYjNjXHVjMWUwXHViOTdjIFx1YjljY1x1YzljMFx1YmE3NCBcdWM3OTBcdWJiM2NcdWMxZTBcdWIyOTQgXHViNTE0XHVjMmE0XHVkNTBjXHViODA4XHVjNzc0XHVjNWQwIFx1YzIyYlx1Yzc5MCBcdWQ1NThcdWIwOThcdWI5N2MgXHViY2Y0XHVjNWVjXHVjOTAwXHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHViOTdjIE5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IDlcdWM3OTBcdWI5YWNcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0IFx1Yzc5MFx1YmIzY1x1YzFlMFx1YjI5NCBcdWM1ZjRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjE3OFx1YjRkY1x1YWMwMCBOXHVhYzFjXHVjNzg4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM2NDAgXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IDFcdWM3NzRcdWIwYjRcdWM3NzRcdWIyZTQuIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI3ODAgXHVhZGY4IFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4ZThcdWQyYjhcdWM2NDAgXHViOWFjXHVkNTA0IFx1YjE3OFx1YjRkY1x1YzY0MFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWMxMlx1Yzc3NFx1YjJlNC4gXHViMTc4XHViNGRjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDBcdWM3NzRcdWFjZTAsIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWM1YzZcdWIyOTQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCAtMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdWJ0cmVlLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM2OHB4OyBoZWlnaHQ6IDI4M3B4O1wiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4IE5cdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gTlx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDE0MjdcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBOXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSA5XHVjNzkwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjMTFjIDlcdWM3OTBcdWI5YWNcdWI4NWMgXHViOWRlXHVjZGIwXHVjNTdjIFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NDU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZSBDb3VudCIsImRlc2NyaXB0aW9uIjoiPHA+T3VyIHN1cGVyaGVybyBDYXJyeSBBZGRlciBoYXMgdW5jb3ZlcmVkIHRoZSBzZWNyZXQgbWV0aG9kIHRoYXQgdGhlIGV2aWwgSGVhZCBDcmFzaCB1c2VzIHRvIGdlbmVyYXRlIHRoZSBlbnRyYW5jZSBjb2RlIHRvIGhpcyBmb3J0cmVzcyBpbiBPYWtsYW5kLiBUaGUgY29kZSBpcyBhbHdheXMgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBiaW5hcnkgc2VhcmNoIHRyZWVzIHdpdGggc29tZSBudW1iZXIgb2Ygbm9kZXMsIHRoYXQgaGF2ZSBhIHNwZWNpZmljIHByb3BlcnR5LiBUbyBrZWVwIHRoaXMgY29kZSBzaG9ydCwgaGUgb25seSB1c2VzIHRoZSBsZWFzdCBzaWduaWZpY2FudCBuaW5lIGRpZ2l0cy48XC9wPlxyXG5cclxuPHA+VGhlIHByb3BlcnR5IGlzIHRoYXQsIGZvciBlYWNoIG5vZGUsIHRoZSBoZWlnaHQgb2YgdGhlIHJpZ2h0IHN1YnRyZWUgb2YgdGhhdCBub2RlIGlzIHdpdGhpbiBvbmUgb2YgdGhlIGhlaWdodCBvZiB0aGUgbGVmdCBzdWJ0cmVlIG9mIHRoYXQgbm9kZS4gSGVyZSwgdGhlIGhlaWdodCBvZiBhIHN1YnRyZWUgaXMgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBwYXRoIGZyb20gdGhlIHJvb3Qgb2YgdGhhdCBzdWJ0cmVlIHRvIGFueSBsZWFmIG9mIHRoYXQgc3VidHJlZS4gQSBzdWJ0cmVlIHdpdGggYSBzaW5nbGUgbm9kZSBoYXMgYSBoZWlnaHQgb2YgMCwgYW5kIGJ5IGNvbnZlbnRpb24sIGEgc3VidHJlZSBjb250YWluaW5nIG5vIG5vZGVzIGlzIGNvbnNpZGVyZWQgdG8gaGF2ZSBhIGhlaWdodCBvZiAmbWludXM7MS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdWJ0cmVlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4M3B4OyB3aWR0aDozNjhweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBiZSBmb3JtYXR0ZWQgYXMgZm9sbG93cy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBvY2N1ciBvbiBpdHMgb3duIGxpbmUuIEVhY2ggbGluZSB3aWxsIGNvbnRhaW4gb25seSBhIHNpbmdsZSBpbnRlZ2VyLCBOLCB0aGUgbnVtYmVyIG9mIG5vZGVzLiBUaGUgdmFsdWUgb2YgTiB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTQyNywgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgb3V0cHV0IGlzIG9uZSBsaW5lIHBlciB0ZXN0IGNhc2UsIGNvbnRhaW5pbmcgb25seSB0aGUgbmluZS1kaWdpdCBjb2RlIChub3RlIHRoYXQgeW91IG11c3QgcHJpbnQgbGVhZGluZyB6ZXJvcykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

채점

  • 제출한 후 다른 소스를 제출하려면 3초가 지나야 한다.