시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB53191542.857%

문제

상근이는 학교 사물함에 매우 비싼 물건을 보관한다. 이렇게 중요한 물건을 학교에 보관하는 이유와 무엇이 그렇게 중요한지는 아직 알려지지 않았다. 하지만, 상근이는 보안을 유지하기 위해서 비밀번호가 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+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHVjNzkwXHViYjNjXHVjMWUwXHVjNWQwXHViMjk0IExFRCBcdWI1MTRcdWMyYTRcdWQ1MGNcdWI4MDhcdWM3NzRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzkwXHViYjNjXHVjMWUwXHViOTdjIFx1YjljY1x1YzljMFx1YmE3NCBcdWM3OTBcdWJiM2NcdWMxZTBcdWIyOTQgXHViNTE0XHVjMmE0XHVkNTBjXHViODA4XHVjNzc0XHVjNWQwIFx1YzIyYlx1Yzc5MCBcdWQ1NThcdWIwOThcdWI5N2MgXHViY2Y0XHVjNWVjXHVjOTAwXHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHViOTdjIE5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IDlcdWM3OTBcdWI5YWNcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0IFx1Yzc5MFx1YmIzY1x1YzFlMFx1YjI5NCBcdWM1ZjRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjE3OFx1YjRkY1x1YWMwMCBOXHVhYzFjXHVjNzg4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMSBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzY0MCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YjBiNFx1Yzc3NFx1YjJlNC4gXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjc4MCBcdWFkZjggXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YzY0MCBcdWI5YWNcdWQ1MDQgXHViMTc4XHViNGRjXHVjNjQwXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhYzEyXHVjNzc0XHViMmU0LiBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVkNTU4XHViMDk4XHVjNzg4XHViMjk0IFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgMFx1Yzc3NFx1YWNlMCwgXHViMTc4XHViNGRjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IC0xXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N1YnRyZWUucG5nXCIgc3R5bGU9XCJ3aWR0aDogMzY4cHg7IGhlaWdodDogMjgzcHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOTggTlx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBOXHVjNzQwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTQyN1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IE5cdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IDlcdWM3OTBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWMxMWMgOVx1Yzc5MFx1YjlhY1x1Yjg1YyBcdWI5ZGVcdWNkYjBcdWM1N2MgXHVkNTVjXHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ0NTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVlIENvdW50IiwiZGVzY3JpcHRpb24iOiI8cD5PdXIgc3VwZXJoZXJvIENhcnJ5IEFkZGVyIGhhcyB1bmNvdmVyZWQgdGhlIHNlY3JldCBtZXRob2QgdGhhdCB0aGUgZXZpbCBIZWFkIENyYXNoIHVzZXMgdG8gZ2VuZXJhdGUgdGhlIGVudHJhbmNlIGNvZGUgdG8gaGlzIGZvcnRyZXNzIGluIE9ha2xhbmQuIFRoZSBjb2RlIGlzIGFsd2F5cyB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IGJpbmFyeSBzZWFyY2ggdHJlZXMgd2l0aCBzb21lIG51bWJlciBvZiBub2RlcywgdGhhdCBoYXZlIGEgc3BlY2lmaWMgcHJvcGVydHkuIFRvIGtlZXAgdGhpcyBjb2RlIHNob3J0LCBoZSBvbmx5IHVzZXMgdGhlIGxlYXN0IHNpZ25pZmljYW50IG5pbmUgZGlnaXRzLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvcGVydHkgaXMgdGhhdCwgZm9yIGVhY2ggbm9kZSwgdGhlIGhlaWdodCBvZiB0aGUgcmlnaHQgc3VidHJlZSBvZiB0aGF0IG5vZGUgaXMgd2l0aGluIG9uZSBvZiB0aGUgaGVpZ2h0IG9mIHRoZSBsZWZ0IHN1YnRyZWUgb2YgdGhhdCBub2RlLiBIZXJlLCB0aGUgaGVpZ2h0IG9mIGEgc3VidHJlZSBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHBhdGggZnJvbSB0aGUgcm9vdCBvZiB0aGF0IHN1YnRyZWUgdG8gYW55IGxlYWYgb2YgdGhhdCBzdWJ0cmVlLiBBIHN1YnRyZWUgd2l0aCBhIHNpbmdsZSBub2RlIGhhcyBhIGhlaWdodCBvZiAwLCBhbmQgYnkgY29udmVudGlvbiwgYSBzdWJ0cmVlIGNvbnRhaW5pbmcgbm8gbm9kZXMgaXMgY29uc2lkZXJlZCB0byBoYXZlIGEgaGVpZ2h0IG9mICZtaW51czsxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N1YnRyZWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjgzcHg7IHdpZHRoOjM2OHB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGJlIGZvcm1hdHRlZCBhcyBmb2xsb3dzLiBFYWNoIHRlc3QgY2FzZSB3aWxsIG9jY3VyIG9uIGl0cyBvd24gbGluZS4gRWFjaCBsaW5lIHdpbGwgY29udGFpbiBvbmx5IGEgc2luZ2xlIGludGVnZXIsIE4sIHRoZSBudW1iZXIgb2Ygbm9kZXMuIFRoZSB2YWx1ZSBvZiBOIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxNDI3LCBpbmNsdXNpdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBvdXRwdXQgaXMgb25lIGxpbmUgcGVyIHRlc3QgY2FzZSwgY29udGFpbmluZyBvbmx5IHRoZSBuaW5lLWRpZ2l0IGNvZGUgKG5vdGUgdGhhdCB5b3UgbXVzdCBwcmludCBsZWFkaW5nIHplcm9zKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d