Alex is a necklace maker. He likes this task because it's challenging, fascinating and of course makes a lot of money. Now, he wants to make a necklace consisting of n beads. The beads are connected in the following fashion:
1) Bead i (1 < i < n) is connected with bead i - 1 and bead i + 1.
2) The first bead is connected with the second bead and the nth bead.
3) The nth bead is connected with the first bead and the (n-1)th bead.
Now he has K colors and each bead can be colored using one of the K colors.He has to find the number of possible necklaces he can make using these colors. Two necklaces will be considered same if one can be rotated to another.
For example, say there are 4 beads in the necklace and he has two colors yellow and green, then there are 6 possible necklaces. They are: