The history of all hitherto existing society is the history of the struggle for better LOL ranks.
— Hungry Santa, 1848
We start with a binary tree consisting of only one node, namely its root. At each step, we can choose a leaf of the current tree and create two new children in that node, namely the left one and the right one. Find the total number of trees of height that can be obtained after applying such operations. The result shall be printed modulo .
The height of a tree is defined as the length (that is, number of edges) of the longest path starting from its root and ending in one of its leaves.
Two binary trees, and , each having more than one node, are considered equal if the left subtree of equals the left subtree of and the right subtree of equals the right subtree of . Two binary trees, each having exactly one node, are always considered equal.
Input
The first line contains the numbers () and ().
Output
The first line contains the required number modulo .
Example 1
stdin
5 3
stdout
6
Example 2
stdin
314 100
stdout
569329628