DEC123 - Decorating the Palace

no tags 

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^ 9 + 7.

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

Input

T: number of test cases (<= 10), then next T lines contain H, N.

Output

Output the number of different decorations % (10 ^ 9 + 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

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-08-03 09:59:46

"child floors will have as less difference between number of flowers in them as possible" This rule causing the problem easier :) (let the semi-BruteForce solution to get AC).

Last edit: 2012-08-03 09:59:24
praveen123: 2012-08-02 18:54:42

@Mitch , Yes it is completely different now , I am really sorry for this .

Mitch Schwartz: 2012-08-02 18:49:51

"Somewhat misleading"? The problem is completely different now.

praveen123: 2012-08-02 18:44:06

@ Tjandra , The problem statement was having a complete different meaning than intended . So I have updated that , Now please reread the statement .
I have also added some more example.

Last edit: 2012-08-02 18:55:37
(Tjandra Satria Gunawan)(曾毅昆): 2012-08-02 18:44:06

@praveen123: Are you sure test data is correct? I've checked my program with brute-force program and found nothing wrong. See my submission ID: 7406556

@Mitch Schwartz: I assume each different node is different floor, but getting WA.

Last edit: 2012-08-02 17:09:05
Mitch Schwartz: 2012-08-02 18:44:06

Given that "Two decorations are considered different if any floor in them contains different no of flowers", I fail to see how the answer can be anything other than 1. Each floor must have the same number of flowers as the top floor. Is there some typo?

devu: 2012-08-02 18:44:06

I dint understand the problem,can anybody explain me the problem with proper test case

Last edit: 2012-08-02 18:16:07

Added by:praveen123
Date:2012-08-02
Time limit:0.104s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general problem