Bracelets

He took up making bracelets out of colored beads. He lays several beads in a row, runs a thread through them, then ties the two ends of the thread together so the beads form a ring. The number of bracelets he could build is enormous, and because he dislikes near duplicates he decided that two bracelets are the same kind whenever rotating or flipping one of them makes the order of bead colors match the other.

The picture above shows a bracelet of four beads with red and blue alternating. Which color you read first splits it into two apparent kinds. Rotating the left bracelet slightly clockwise produces the same arrangement as the right one, so the two count as a single kind.

The picture above shows bracelets of five beads. Flipping the left bracelet left to right produces the right one, so these two also count as a single kind.

He has $K$ colors of beads, with an unlimited supply of each color. Write a program that counts the distinct kinds of bracelets he can make using at most $N$ beads. The bracelet that uses no beads at all counts as one kind.

The first line has two integers $N$ and $K$, separated by a space: the number of beads he may use and the number of bead colors. ($1 \le N \le 10^6$, $1 \le K \le 10^6$)

Print on the first line how many kinds of bracelets can be made using at most $N$ beads. The count grows very large, so print it modulo 1,000,000,007.