eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

АВЛ-дерева

АВЛ-дерева

АВЛ-дерево --- збалансоване по высоті двійкове дерево пошука: для кожної його вершини висота його двох піддерев відрізняється не більше ніж на \textbf{1}. АВЛ-дерева названі за першими літерами прізвищ їх винахідників, Г. М. Адельсона-Вельского та Е. М. Ландіса. Для фіксованої кількості вершин може існуватиь декілька АВЛ-дерев. Наприклад, існує шість АВЛ-дерев, які складаються з п'яти вершин. \includegraphics{https://static.e-olymp.com/content/e9/e9b2f0f45aede1674ff4fd2aca6c4fbb7affc96d.jpg} Також дерева з однаковою кількістю вершин можуть мати різну висоту. Наприклад, існують дерева з семи вершин з висотами \textbf{2} і \textbf{3} відповідно. \includegraphics{https://static.e-olymp.com/content/3e/3eb13f6f7830dd7beeb072f0a29aeb21a49336d7.jpg} Потрібно за заданими \textbf{n} і \textbf{h} знайти кількість АВЛ-дерев, які складаються з \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{n} вершин і мають висоту \textbf{h}, на \textbf{786433}.
Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
7 3
Вихідні дані #1
16

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

Автор Дмитро Жуков
Джерело Зимова Школа, Харків 2011, День 2