Problem1249--AVL树的种类

1249: AVL树的种类

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 28  Solved: 22
[Submit] [Status] [Web Board] [Creator:]

Description

平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。 现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。

Input 

一行，包含一个整数n。 (0 < n <= 2000)

Output 

一行表示结果，由于结果巨大，输出它对1000000007取余数的结果。

Sample Input 

10

Sample Output 

60

Source/Category

中等 动态规划 
[Submit] [Status]