From Board to Board

Bajtazar, who wanted contact with nature and an escape from the noise of the city, became a lumberjack in the Bajtomil forest. His current job is to cut $n$ specific trees growing in a straight row that runs from west to east. Each tree belongs to one of $m$ species, but he is only starting out and makes mistakes, so he does not remember which tree is which species.

Each day he picks an uncut tree and walks east from it, cutting every uncut tree he passes. He must finish his work for the day right after cutting a tree of the same species as the tree where he started that day (it does not have to be the first tree of that species he meets). The cut logs are gathered and loaded in the order they were cut, and the load looks neat only this way. He also wants to cut at least two trees each day so it does not look like he is slacking.

Not every tree can always be cut. It depends on which trees belong to which species. Count the number of possible species sequences for which Bajtazar can cut all the trees after some number of days. Two sequences are different if at least one tree belongs to a different species in one sequence than in the other. Output the answer modulo $10^9+7$.

The only line contains two integers $n$ and $m$ ($1 \le n \le 3000$, $1 \le m \le 10^9$): the number of trees to cut and the number of species the trees may belong to.

Print one integer: the number of possible species sequences, modulo $10^9+7$.

Explanation of the example: if the species are labeled 1 and 2, the species sequences for which Bajtazar can finish 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