#P15675. [Bulgarian2023训练营]Avl

[Bulgarian2023训练营]Avl

题目描述

AVL 树是一种平衡的有根二叉树:对于每个结点,它的左子树高度与右子树高度之差至多为 11。AVL 树以其发明者 Adelson-Velskiy 和 Landis 命名。

对于给定的结点数,可能存在多棵不同的 AVL 树。例如,含有 55 个结点的 AVL 树共有 66 棵。并且,对于相同的结点数,AVL 树也可能有不同的高度。例如,含有 77 个结点的 AVL 树的高度可以是 22 或 33。

给定 nn 和 hh,求有多少棵 AVL 树恰好有 nn 个结点且高度为 hh。由于答案可能很大,请输出答案对 786433786433 取模后的结果。

输入格式

输入包含两个整数 n,hn,h。

输出格式

输出一个整数,表示有 nn 个结点且高度为 hh 的 AVL 树数量,答案对 786433786433 取模。

数据范围

1≤n≤65535,0≤h≤151\le n\le 65535,\qquad 0\le h\le 15

样例

输入

7 3

输出

16

说明

786433786433 是质数,并且

786433=3⋅218+1.786433=3\cdot 2^{18}+1.