시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 18 8 8 80.000%

문제

한양대학교는 크리스마스 즈음이 되면 애지문에 트리를 꾸며 놓는다. 그리고 이번 년도에는 김하냥이 크리스마스 트리 꾸미기를 맡게 되었다. 하지만 김하냥은 트리라고는 이진트리 밖에 모르는 이진트리 바보이다. 그래서 김하냥은 애지문에 놓을 트리를 이진트리 모양으로 꾸미고 싶어 한다.

한양대에서는 김하냥에게 장식으로 '트리 볼'만을 제공한다. 하지만 이 볼의 개수에는 제한이 있고, 꾸며야 할 트리의 높이 또한 정해져 있다. 한양대에서 트리의 높이를 제한해 준다면, 김하냥은 꼭 그 트리 높이만큼의 트리를 만들어야 한다. 트리가 그 높이보다 작거나 클 수 없고, 볼도 한양대에서 제한해 준 개수로만 사용 가능하다. 또한 제공된 '트리 볼'도 반드시 모두 사용해야 한다.

김하냥은 볼의 개수와 트리의 높이에 제한이 있을 때, 자신이 트리를 꾸밀 수 있는 경우의 수가 궁금해졌다. 이진트리 밖에 모르는 김하냥을 위해 우리 한양대생들이 도와주자!

예를 들어, 볼의 개수가 5이고, 트리의 높이가 3이라면 트리를 꾸밀 수 있는 경우의 수는 다음과 같다. 

입력

첫째 줄에 볼의 개수 N과 트리의 높이 L이 차례대로 주어진다. (1 ≤ N ≤ 300, 1 ≤ L ≤ 300) 

출력

트리를 꾸밀 수 있는 경우의 수를 100,030,001로 나눈 나머지를 출력한다. 

예제 입력 1

5 3

예제 출력 1

6

예제 입력 2

6 4

예제 출력 2

40

힌트

이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에서 d번째 줄엔 2d−1개의 노드가 있을 수 있다.