Bajtazar, longing for contact with nature and a break from the city bustle, has become a lumberjack in the Bajtomilowy forest. His current task is to cut down $n$ specific trees growing in a straight line, stretching from west to east. Additionally, he knows that each tree belongs to one of $m$ species, but since he is still taking his first steps in the world of logging and occasionally makes mistakes, he does not remember which tree belongs to which species.
He decided that each day he will start at some as-yet-uncut tree and begin walking east, cutting down all uncut trees he encounters along the way. He must finish his work for the day immediately after cutting down a tree of the same species as the tree at which he started that day's logging (though it does not necessarily have to be the first tree of that species he encounters). He must do this because the cut trunks are collected and packed in the order they are cut, and the load looks simply aesthetic that way. Additionally, he would like to cut down at least two trees each day so as not to give the impression that he is slacking off at work.
However, he will not always be able to cut down all the trees – this undoubtedly depends on which trees belong to which species. Bajtazar wonders how many possible sequences of tree species exist for which (after any number of days) he is able to cut down all the trees. Two sequences of species are considered different if there exists at least one tree that belongs to a different species in one sequence than in the other.
Help him and write a program that will calculate this number. Since it can be very large, it is sufficient to provide its remainder when divided by $10^9 + 7$.
Input
The first and only line of input contains two integers $n$ and $m$ ($1 \le n \le 3000$, $1 \le m \le 10^9$).
They denote, respectively, the number of trees to be cut and the number of possible species to which they can belong.
Output
The output should contain a single integer, which is the remainder of the number of possible tree species sequences when divided by $10^9 + 7$.
Examples
Input 1
4 2
Output 1
10
Note
If we denote the species with the numbers 1 and 2, the possible sequences of tree species for which Bajtazar is able to finish his work successfully are:
- 1, 1, 1, 1
- 1, 1, 2, 1
- 1, 1, 2, 2
- 1, 2, 1, 1
- 1, 2, 2, 1
- 2, 1, 1, 2
- 2, 1, 2, 2
- 2, 2, 1, 1
- 2, 2, 1, 2
- 2, 2, 2, 2