Game Addiction

Interview

Time limit1sMemory limit1024 MB

Summary

Count shortest lattice paths between two diagonal points while staying inside the unflooded region y <= x.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Gangsan is a serious game addict, so he goes to the PC bang every day no matter the weather.

Recent heavy rain flooded some areas, and he cannot move into flooded areas. Even so, Gangsan must go to the PC bang every single day for the attendance event.

Gangsan moves to the PC bang only in the up, down, left, and right directions, and each move has distance 1. He also wants to play his game quickly, so he moves from home to the PC bang along a shortest path.

Given the coordinates of Gangsan's home $(H, H)$ and the PC bang $(N, N)$ , and given that a point $(x, y)$ on the coordinate plane is flooded when $y > x$ , find the number of paths Gangsan can take to reach the PC bang while avoiding flooded areas.

If the PC bang has the same coordinates as his home, the number of paths is 1.

Input

The first line gives two integers $H$ and $N$ ( $0 \le H, N \le 30$ ), the coordinates of the home $(H, H)$ and the PC bang $(N, N)$ , in that order.

Output

Print the number of paths from home to the PC bang.

Examples2

Example 1
Input
```
8 4
```
Expected output
```
14
```
Example 2
Input
```
0 3
```
Expected output
```
5
```