Sunday Coding

Time limit2sMemory limit512 MB

Summary

Count the distinct sequences of room-winner ranks obtainable when R rooms each hold S contestants with all ranks distinct.

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

Problem

Yeongseon is entering the online programming contest "Sunday Coding".

While the contest runs, the participants are split into $R$ rooms and each room holds $S$ participants, so there are $R \times S$ participants in total. The rooms are numbered from $1$ to $R$ .

Nobody ties, so once the contest ends every participant receives a distinct rank from $1$ (the overall win) to $R \times S$ .

The winner of a room is the participant with the best rank in that room.

After the contest Yeongseon writes down the rank of each room winner in room order, which gives a sequence of length $R$ . The $i$ -th number of the sequence is the rank of the winner of room $i$ .

Given $R$ and $S$ , write a program that counts the different sequences that can be produced this way.

Input

The first line contains $R$ and $S$ , separated by a space. ( $1 \le R, S \le 100$ )

Output

On the first line, print the number of different sequences that can be produced, modulo 1,000,000,007.

Hint

For $R = 2$ and $S = 1$ there are two rooms with one participant each, so the sequence is either $(1, 2)$ or $(2, 1)$ .

For $R = 2$ and $S = 2$ the sequences that can be produced are $(1, 2)$ , $(2, 1)$ , $(1, 3)$ , $(3, 1)$ . Neither $(2, 3)$ nor $(1, 4)$ is ever possible.

Examples4

Example 1
Input
```
2 1
```
Expected output
```
2
```
Example 2
Input
```
1 2
```
Expected output
```
1
```
Example 3
Input
```
2 2
```
Expected output
```
4
```
Example 4
Input
```
4 5
```
Expected output
```
6840
```