1404. Broken Necklace — Bitmask Circular DP

A necklace has n beads arranged in a circle, and each bead is painted with one of k colours. Count the colourings in which no two adjacent beads (including the wrap-around pair joining the last and first bead) share the same colour, and return the count modulo 1000000007.

Input: A JSON object {"n": <number of beads>, "k": <number of colours>}.

Output: Return the number of valid cyclic colourings modulo 1000000007.

Examples

Input: {"n":3,"k":3}
Output: 6
Explanation: A triangle has 6 proper 3-colourings.

Input: {"n":4,"k":3}
Output: 18
Explanation: A 4-cycle has 18 proper 3-colourings.

Constraints

• 2 <= n <= 10^9
• 1 <= k <= 10^9

Asked by