Problem Statement

You have a sufficient supply of identical planks. Each plank has the shape of an 1 times H
rectangle.

The floor of your room is also a rectangle. Its width is W and its height is 2H-1. You want to use
the planks you have to tile the floor. The entire floor must be covered and the planks must not
overlap. (The width W is guaranteed to be a multiple of H, so this is always possible.)

You are given the two ints H and W. Return the number of ways to tile the floor, modulo 1,000,000,007.

Method signature: int sumup(int H, int W)
Time limit (s): 2.000
Memory limit (MB): 256

Constraints

- H will be between 2 and 1000, inclusive.
- W will be between 2 and 1000, inclusive.
- W will be multiple of H.

Examples

0)

2
4
Returns: 11

We are using 1x2 planks to tile a rectangle of width 4 and height 3. There are eleven different ways
to do so:

(a figure is here, with pictures like this one:
1144  1155
2256  2336
3356  2446)


1)

4
4
Returns: 5


2)

3
9
Returns: 121


3)

29
841
Returns: 193514715


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.