eolymp
bolt
Try our new interface for solving problems
Problems

AVL-trees

AVL-trees

AVL tree - a balanced height binary search tree: for each vertex height of its two subtrees differ by no more than \textbf{1}. AVL-trees are named by the first letters of the names of their inventors, G.M.Adelson-Belsky and E.M.Landis. For a fixed number of vertices can have multiple AVL-trees. For example, there are six AVL-trees consisting of five peaks. \includegraphics{https://static.e-olymp.com/content/e9/e9b2f0f45aede1674ff4fd2aca6c4fbb7affc96d.jpg} Also, trees with the same number of vertices can be of different heights. For example, there are trees of the seven peaks with heights of \textbf{2} and \textbf{3}, respectively. \includegraphics{https://static.e-olymp.com/content/3e/3eb13f6f7830dd7beeb072f0a29aeb21a49336d7.jpg} Required for a given \textbf{n} and \textbf{h} to find the number of AVL-trees, consisting of \textbf{n} vertices and with a height \textbf{h}. Because the answer may be very large, we must find the remainder after dividing the desired amount to \textbf{786433}. \InputFile In the input file are integers \textbf{n} and \textbf{h} (\textbf{1} ≤ \textbf{n} ≤ \textbf{65535}, \textbf{0} ≤ \textbf{h} ≤ \textbf{15}). \OutputFile Bring out one number - the remainder of the division of AVL-trees, consisting of \textbf{n} vertices and with a height \textbf{h}, at \textbf{786433}.
Time limit 5 seconds
Memory limit 256 MiB
Input example #1
7 3
Output example #1
16

Example description: 786433 - prime number, 786433 = 3*2^18 + 1

Author Dmitriy Zhukov
Source Winter School, Kharkov, 2011, Day 2