Background

N 个 相同/不同 的球放到 M 个 相同/不同 的盒子里，允许/不允许 有空盒子，有多少种放法？

Description

N 个 不同 的球放到 M 个 相同 的盒子里，不允许 有空盒子，有多少种放法？

答案可能很大，你需要将其 mod (10^9+7) 后输出。

Format

Input

一行，包含两个整数 N, M

Output

一个整数，表示答案

Samples

3 2

3

456 123

896809103

DataSize

1 ≤ N, M ≤ 10^3