For his thirteenth birthday, Donald's parents bought him a brand-new set of Lego cubes. In the set, there are cubes of equal size, where the -th cube has color . Using these cubes he decided to build a wall.

Donald will build his wall on a row-like Lego base that has places where cubes can be put in. He puts the cubes in the following way:

- First, he puts the cube with color on an arbitrary spot on the base.
- For each cube from to , he places it in a spot neighboring the previously placed cube. If that spot isn't empty, he puts the new cube on top of all the others.

After he built the wall, Donald wrote on a piece of paper a sequence of length : in the -th position in the sequence he wrote the color of the top cube in the -th place, or if there isn't a cube in that place.

He immediately asked himself how many different sequences could he have written on the piece of paper. Two sequences are considered different if there exists a position in which they differ. After some time, he has managed to calculate the solution, but he is not sure whether it is correct, so he asks for your help.

#### Input Specification

The only line has integers and , the number of cubes, and the length of the base.

#### Output

In the only line, print the answer to Donald's question, modulo .

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 20 | |

2 | 30 | |

3 | 30 | |

4 | 30 | No additional constraints. |

#### Sample Input 1

`4 3`

#### Sample Output 1

`8`

#### Explanation for Sample 1

All possible sequences are: .

#### Sample Input 2

`3 5`

#### Sample Output 2

`14`

#### Sample Input 3

`100 200`

#### Sample Output 3

`410783331`

## Comments