After collecting a bountiful harvest of nuts to last him throughout the winter, Clifford the Squirrel has decided to make some of them into a necklace so that he can easily carry them around. However, as a fashionable squirrel, he needs help choosing the necklace's design.

Clifford would like to make a necklace consisting of ~N~ nuts arranged in a single closed cycle such that each nut is one of the ~M~ types that he has collected. Please help him find the number of different necklace designs, modulo ~10^9+7~, satisfying the following requirements:

1. No two adjacent nuts in the design have the same type.
2. Necklaces that are rotations of each other count as a single design.

For example, if ~N = 4~ and ~M = 4~, ~[1, 2, 3, 4]~ and ~[3, 1, 3, 2]~ are valid designs while ~[1, 2, 3, 3]~ and ~[1, 2, 3, 1]~ are invalid designs under requirement ~1~. Also, ~[1, 2, 3, 4]~ is the same design as ~[4, 1, 2, 3]~, ~[3, 4, 1, 2]~, and ~[2, 3, 4, 1]~ under requirement ~2~ because they are cyclic shifts of each other.

Constraints

For all subtasks:

~3 \le N \le 10^{12}~

~2 \le M \le 10^9~

It is guaranteed that ~N~ will not be a multiple of ~10 ^ 9 + 7~.

Subtask 1 [10%]

~N = 3~

Subtask 2 [10%]

~N \le 10^5~

~N~ is guaranteed to be prime.

Subtask 3 [30%]

~N \le 10^5~

Subtask 4 [50%]

No further constraints.

Input Specification

The first line will contain two space-separated integers, ~N~ and ~M~.

Output Specification

Output one integer, the number of different necklace designs modulo ~10^9+7~.

Sample Input 1

3 3

Sample Output 1

2

Explanation for Sample Output 1

The two valid designs are ~[1, 2, 3]~ and ~[3, 2, 1]~. Note that all other valid arrangements are just rotations of these designs. For example, ~[2, 3, 1]~ is a rotation of ~[1, 2, 3]~.

Sample Input 2

5 4

Sample Output 2

48

Sample Input 3

8 6

Sample Output 3

48915