상근이의 자물쇠

어떤 자물쇠는 9자리 숫자를 비밀번호로 사용한다. 자물쇠를 만지면 LED 디스플레이에 정수 하나 $N$이 나타난다. 아래 조건을 만족하는 트리의 개수를 구한 뒤, 그 값의 마지막 9자리를 입력하면 자물쇠가 열린다.

노드가 $N$개인 이진 트리를 생각하자. 이 트리의 모든 노드에 대해, 그 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 $1$ 이하여야 한다. 서브트리의 높이란 그 서브트리의 루트에서 리프 노드까지 이르는 경로의 길이 중 가장 긴 값이다. 노드가 하나뿐인 서브트리의 높이는 $0$이고, 노드가 하나도 없는(비어 있는) 서브트리의 높이는 $-1$이다.

서로 다른 트리의 모양이 몇 개인지 세면 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $N$ 하나로 이루어지며, $1 \le N \le 1427$이다. 입력은 파일의 끝까지 계속된다.

각 테스트 케이스마다, 주어진 $N$에 해당하는 트리의 개수의 마지막 9자리를 한 줄에 출력한다. 자릿수가 9자리에 미치지 못하면 앞을 $0$으로 채워 정확히 9자리가 되도록 출력한다.