Biving lives in Grid Kingdom, which is a special country as all its cities lie in a grid of size W*H.
Biving’s home locates in grid(1, 1) and she wants to go to grid(W, H) as soon as possible. In each step, she can walk from grid(I, J) to grid(I+1, J) or grid(I, J+1), but she can never walk out of the grid.
Here comes the question, how many path Biving can choose to achieve her goal. Two path Pi and Pj are treat as different if there exist some step Pi going to grid(x, y) but Pj don’t.