The King of DragonLand likes decorating towers. So one day he decided to decorate a tower with flowers.

The highest floor of a tower contains only one room and floor just below every floor except the base floor will have two of its child buildings on which it is built.

Note that its structure is like a binary tree.

for height = 3

              *
           *     *
          * *   * *

You are given the task of decorating it, but there is a constraint in decorating it: sum of child floors of a floor will have be equal to number of flowers in parent building and your child floors will have a small a difference between number of flowers in them as possible to make your tower look beautiful.

Given that top building contains N flowers and height of tower is H, find out number of ways of decorating it, As this value may be large, output it modulo 10⁹ + 7.

Two decorations are considered different if any floor in them contains different number of flowers

Input

Output

Output the number of different decorations % (10⁹ + 7)

Constraints

1 ≤ H ≤ 50

1 ≤ N ≤ 50000

Example

Input
2
1 1
2 1

Output
1
2

Explanation

for 1 1, it is obvious.

for 2 1,

There can be two ways:

   1
1     0

OR

   1
0     1