G. Beautiful Crown
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Technoblade is also famous for having a beautiful crown. Now he wants to make new crowns, one with $$$K$$$ spaces for jewels, where he can place any of the $$$M$$$ types of jewels known to him.

Techno was surprised by the number of options and is now curious to know how many crowns of size $$$K$$$, using $$$M$$$ types of jewels, exist. All jewels of the same type are identical, and two jewels of different types are always distinguishable. Note also that if a crown can be rotated so that it looks the same as another, they are considered identical.

Since Techno has not decided on the value of $$$K$$$, he is interested in the sum of the number of crowns for all $$$K$$$ from $$$1$$$ to $$$N$$$. As this number is large, print modulo $$$10^9+7$$$.

Input

The input consists of only two integers $$$N$$$ and $$$M$$$, $$$1 \leq N, M \leq 10^6$$$.

Output

Print a single line containing the number of possible crowns with size from 1 to $$$N$$$, using $$$M$$$ types of jewels.

Examples
Input
1 2
Output
2
Input
2 2
Output
5
Input
10 3
Output
9503
Input
1000 1000000
Output
250445517