상근이의 자물쇠

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

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

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

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

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