eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

AVL

\textbf{AVL} деревья, придуманные российскими учёными Адельсон-Вельским и Ландисом, являются примером сбалансированного бинарного дерева поиска. В терминологии \textbf{AVL}, подвешенное бинарное дерево называется \textit{сбалансированным}, если для каждой вершины высоты её левого и правого поддеревьев отличаются не более, чем на один. Такое дерево, собственно, и называется \textit{AVL}-\textit{деревом}. Разумеется, существует далеко не единственное \textbf{AVL}-дерево при фиксированном числе вершин. К примеру, существует шесть \textbf{AVL}-деревьев с пятью вершинами, они изображены на рисунке ниже. \includegraphics{https://static.e-olymp.com/content/80/8043cf2c9639bfbc787556640f411b2db2c69455.jpg} Деревья с одинаковым числом вершин могут иметь разную высоту, к примеру, на рисунке снизу нарисовано два дерева с семью вершинами, которые могут иметь высоты \textbf{2} и \textbf{3}, соответственно. \includegraphics{https://static.e-olymp.com/content/80/8076038afe93316c76d61dc59964205c3614ee4b.jpg} Вам даны два числа - \textbf{N} и \textbf{H}, требуется найти число \textbf{AVL}-деревьев, которые состоят из \textbf{N} вершин и имеют высоту \textbf{H}. Поскольку их число довольно велико, выведите искомое количество по модулю \textbf{786433}. \InputFile Единственная строка входного файла содержит два числа - \textbf{N} и \textbf{H} (\textbf{1} ≤ \textbf{N} ≤ \textbf{65535}, \textbf{0} ≤ \textbf{H} ≤ \textbf{15}). \OutputFile Выведите единственное число - количество \textbf{AVL}-деревьев с \textbf{N} вершинами высоты \textbf{H}, по модулю \textbf{786433}.
Лимит времени 2 секунды
Лимит использования памяти 256 MiB
Входные данные #1
7 3
Выходные данные #1
16

Объяснение: 786433 простое число, 786433 = 3 * 2^18 + 1