Time Limit : sec, Memory Limit : KB

# Balls and Boxes 7

BallsBoxesAny wayAt most one ballAt least one ball
DistinguishableDistinguishable123
IndistinguishableDistinguishable456
DistinguishableIndistinguishable789
IndistinguishableIndistinguishable101112

## Problem

You have $n$ balls and $k$ boxes. You want to put these balls into the boxes.

Find the number of ways to put the balls under the following conditions:

• Each ball is distinguished from the other.
• Each box is not distinguished from the other.
• Each ball can go into only one box and no one remains outside of the boxes.
• Each box can contain an arbitrary number of balls (including zero).

Note that you must print this count modulo $10^9+7$.

## Input

$n$ $k$


The first line will contain two integers $n$ and $k$.

## Output

Print the number of ways modulo $10^9+7$ in a line.

## Constraints

• $1 \le n \le 1000$
• $1 \le k \le 1000$

## Sample Input 1

3 5


## Sample Output 1

5


## Sample Input 2

5 3


## Sample Output 2

41


## Sample Input 3

100 100


## Sample Output 3

193120002