Hide

Ghostbusters 3

There is something strange in the neighbourhood. Who you gonna call? Ghostbusters!

A number of ghosts have decided to roam the street, and the Ghostbusters have arrived to deal with this situation. Luckily all the ghosts have decided to stay on one side of a very long street, so it is safe for the Ghostbusters to stand on the opposite side of the street to aim and fire their particle beams at the ghosts. Each Ghostbuster must aim at exactly one ghost, and it is important that the beams do not cross. Two beams are not considered to be crossing each other if they are both aimed at the same ghost.

How many ways are there to assign ghosts to the Ghostbusters, so that as many ghosts as possible are assigned to some Ghostbuster? Of course, no two beams can cross each other. As the answer may be very large, please report the answer modulo $10^9+7$.

Input

There is one line of input containing two integers, $n$ and $m$, with $1\le n\le 1\, 000$ and $1\le m\le 1\, 000$, indicated the number of Ghostbusters and the number of ghosts, respectively.

Output

Output the total number of ways ghosts can be assigned to Ghostbusters as described in the problem statement, modulo $10^9+7$.

Sample Input 1 Sample Output 1
2 5
10
Sample Input 2 Sample Output 2
3 3
1
Sample Input 3 Sample Output 3
5 2
4
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.5hard
Statistics Show
Author
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in