Alien microbes

Count the breeding patterns over H days starting from one microbe, where each day the microbes alive produce children with a total of at most W.

Hard8Dynamic programmingCombinatoricsRecursionMathInterviewNo attempts yetTime limit2sMemory limit256 MB

Problem

Yoonyoung looked at a transcript full of B and C grades, decided she had no talent for computer science, switched to a double major in aerospace engineering and biology, and became a successful researcher of alien life.

On one planet she found an unusual alien microbe and carried a few of them back to her lab. Her study showed that the microbe has the following properties.

  1. A microbe produces children on its own. It produces all of its children during one day and dies that same day. Each microbe freely decides how many children to produce. Children are told apart by the order in which they are produced, and a child starts producing children of its own on the day after it is born.
  2. The microbes do not want their children to compete too hard with each other. They cooperate so that the total number of children produced by the microbes alive on a given day is at most WW. The value of WW stays the same across generations.
  3. A microbe may produce no children at all, but to keep the species going the case where every microbe alive that day produces no children never happens. A microbe that produces no children still dies the day after it was born.

Yoonyoung enjoyed watching this creature breed, so she put a single microbe into a container in her lab. In that container the total number of children allowed without too much competition is WW, and the microbe started breeding.

Microbes alive on the same day are told apart from each other. The pattern of one day is the sequence of child counts of the microbes alive that day, written in the order of the microbes, and a pattern over HH days is HH such sequences listed in day order. Two patterns count as different if they differ on any day.

Starting from a single microbe, count the breeding patterns that can appear over HH days.

Input

The first line contains HH and WW, separated by a space. 0H50 \le H \le 5 and 1W2001 \le W \le 200.

Output

Print, on the first line, the number of breeding patterns over HH days modulo 1,000,000,0071{,}000{,}000{,}007. The count grows large, so an intermediate value can exceed the range of a 32 bit integer. A 64 bit integer is the safe choice.

Hint

For H=1H = 1 and W=3W = 3 the first microbe can produce 1, 2, or 3 children, which gives three patterns. Producing 0 children is ruled out by property 3.

For H=0H = 0 no breeding happens, so the only pattern is the empty one and the answer is 1.