You are given the task to design a giant Ferris Wheel with N cabins for the Garden of Wonderland. You have been provided with an unlimited supply of K colors. You have to color each of the cabins using these K colors.   

Two wheels are considered to be distinct if one of the wheels cannot be obtained from the second wheel by rotating the second wheel by any angle.

Find the total number of distinct necklaces modulo 10⁹+7.

Input Format
A single line consisting of two space-seperated integers, N and K .

Output Format
A single line consisting of the integer denoting the number of distinct necklaces modulo 10⁹+7.

Constraints

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

Sample Input

5 2

Sample output

8

Explanation :