Counting Unique Necklaces

You are given two integers c and k, where c represents the number of available colors and k represents the length of a necklace. A necklace is a sequence of k beads where each bead is colored using one of c colors.

The task is to count the number of unique necklaces that can be formed such that no two adjacent beads have the same color. Since the answer can be very large, output the count modulo \(10^9+7\).

Note: A valid necklace must satisfy the condition that for all adjacent beads, the colors are different. When k = 1, any bead (color) is a valid necklace.

inputFormat

The input consists of a single line containing two space-separated integers c and k.

• c (1 \(\leq c \leq 10^9\)): the number of colors.
• k (1 \(\leq k \leq 10^9\)): the length of the necklace.

outputFormat

Output a single integer representing the number of valid necklaces modulo \(10^9+7\>.

2 1

2