In general, "stateful" transitions are hard to calculate in a loop. Hence, we begin by "unravelling" the necklace into a sequence of ~N~ integers from ~1~ to ~M~ such that no two adjacent elements are equal. Additionally, the first and last element cannot be the same, and we must also account for overcounting (since in a necklace ~ABA~ is equivalent to ~AAB~ as rotations are considered the same).

We start by calculating the number of such sequences. Because of the additional constraint of the last element not being equal to the first, we will handle the two cases separately. Let ~D_i~ be the number of sequences of length ~i~ such that no two adjacent elements are the same and the first element is different from the last element. Let ~S_i~ by the number of sequences of length ~i~ such that no two adjacent elements are the same but the first is the same as the last element.

Then, ~D_i=S_{i-1}\cdot (M-1)+D_{i-1}\cdot (M-2)~ (If the first and last elements are the same, just take one that isn't the last element; if the first and last elements are different, we can't choose the first or last element)

and ~S_i=D_{i-1}~ (since no two elements are adjacent, we must have a sequence where the last element isn't the same as the first add a bead of the first color to the sequence).

Now, we go back to our original problem. We must convert our sequences to a necklace. However, we must now consider rotations. Let's say the shortest period is of length ~P~. Then, there are ~P~ overcounted sequences and we must divide by ~P~.

For example, if ~P~ is ~3~ and ~N~ is ~9~, then the sequences ~ABCABCABC~, ~BCABCABCA~, and ~CABCABCAB~ are all equivalent (they're rotations of each other, but each counted as a separate sequence).

Now, we must solve the problem separately once again. How many sequences of length ~N~ are there such that the shortest period is of length ~P~? Consider this: Take a sequence of length ~P~, and clone it ~\frac NP~ times to get a sequence of length ~N~. Obviously, this sequence must have a period of length ~P~, so the number of sequences of length ~N~ with a period of ~P~ is equal to ~D_P~. However, it might not be the shortest, but if the shortest period isn't of length ~P~, then it must be a divisor of ~P~. So, we can subtract all all sequences with a length equal to a divisor of ~P~.

More formally, if ~Q_P~ is the number of sequences of length ~N~ with a shortest period of ~P~, then ~Q_P=D_P-\sum (Q_i\text{, where }i|P)~

Now finally, there are ~\frac{Q_P}{P}~ possible necklaces (since each necklace has ~P~ "rotations" that are counted in the ~Q_P~ sequences).

So, to reiterate, we wish to find the sum of ~\frac{Q_P}{P}~, we can actually optimize this by only considering ~P~ such that ~P|N~, since ~P~ is the period. Additionally, ~Q_P~ can be calculated if we know ~D_P~ and ~Q_i~ for all ~i|P~. Notice that if ~i|P~, then ~i|N~ as well. So, ~Q_P~ really only relies on other values of ~Q_P~. So, we only need to calculate the value of ~P~ such that ~P|N~. In general, there really aren't that many divisors of a number - in fact it works out to be roughly ~7000~ divisors at most. So, we can run an ~O(D^2)~ algorithm, where ~D~ is the number of divisors. For each value of ~Q_P~, we will first calculate ~D_P~ and iterate through all of the remaining divisors of ~N~, subtracting ~Q_i~ if ~i|P~. Then, once ~Q_P~ is calculated, we add ~\frac {Q_P}{P}~ to our total.

Now, firstly, to get the list of divisors, we can iterate from ~1~ to ~\sqrt N~. If ~j|N~, then we add ~j~ and ~\frac Nj~ to our list of divisors.

Next, to calculate ~D_P~, we must use matrix exponentiation. To begin, we define the transition:

~D_P=S_{P-1}\cdot (M-1)+D_{P-1}\cdot (M-2)~ and ~S_P=D_{P-1}~

So, ~\begin{pmatrix}D_P\\S_P\end{pmatrix}=\begin{bmatrix}M-2&M-1\\1&0\end{bmatrix}\begin{pmatrix}D_{P-1}\\S_{P-1}\end{pmatrix}~. We then take ~\begin{bmatrix}M-2&M-1\\1&0\end{bmatrix}^{P-1}~ and multiply that by ~\begin{pmatrix}D_1\\S_1\end{pmatrix}~ to get ~D_P~. And we are done.