AVL-trees#1846

AVL-trees

5 seconds
256 megabytes
Very easy

AVL-tree — a balanced binary search tree by height: for each vertex, the heights of its two subtrees differ by no more than . AVL-trees are named after the inventors G. M. Adelson-Velsky and E. M. Landis, using the first letters of their surnames.

For a given number of vertices, there may be several different AVL-trees. For example, there are six AVL-trees with five vertices.

Also, trees with the same number of vertices can have different heights. For example, there are trees with seven vertices of heights and .

Given and , find the number of AVL-trees with vertices and height . Since the answer can be very large, output the remainder of dividing this number by .

Input

The input contains integers and (1 \leq n \leq 65535, 0 \leq h \leq 15).

Output

Print one number — the remainder of the number of AVL-trees with vertices and height divided by .

Examples

Example 1

Loading
Loading