**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to count the number of different necklaces that consist of n pearls and each pearl has m possible colors.

Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.

# Input

The only input line has two numbers n and m: the number of pearls and colors.

# Output

Print one integer: the number of different necklaces modulo 10^9+7.

# Constraints

- 1 \le n,m \le 10^6

# Example

Input:

4 3

Output:

24