Code Permutations

You are soon to graduate from the mathemagician school of Hagworts, and you're quite pleased with yourself; all your hard work has finally paid off. Being successful at most of your endeavors, you would normally end up as a herald of sound reasoning and good mathemagics. You, however, are different; not only have you spent your early years secretly hacking away at computers, writing code to do your routine homework for you, but of late you have begun planning to cram all your mathemagical skills into a computer, to completely eliminate the need for mathemagicians! To show the others just how much of a visionary you are, you plan to make your graduation ceremony something they will never forget.

To do this, you need to break into the safe of your arch-nemesis, Hairy Peter. The safe is locked by a code mechanism: all natural numbers from $1$ to $N$ must be entered in the correct order, set by Hairy Peter. Fortunately, you know that Hairy, being a good mathemagician, has a certain weakness: he is unhealthily obsessed with the number $K$. (For instance, he always has to introduce himself $K$ times whenever he meets new people, which makes him rather annoying to be around.) Thus, you are certain that his code, when viewed as a permutation of the first $N$ natural numbers, has order exactly $K$. (That is, $K$ is the smallest positive number such that if you $K$ times replace x \in \{1, \ldots, N\} with the position of $x$ in Hairy's code, you end up with the $x$ you started with, for all $x$. For example, the order of the permutation corresponding to the code $2$ $3$ $1$ is $3$, because 1 \to 3 \to 2 \to 1, 2 \to 1 \to 3 \to 2, and 3 \to 2 \to 1 \to 3.) While this does not help you directly, it greatly reduces the number of code inputs you may have to try before you find the correct one. "How many?" is the question you are pondering right now. You must know the exact number, lest you risk preparing too little time for cracking the safe.

Now, you also have a certain mathemagical weakness—perhaps a bit worse than Hairy Peter's: Because of your dark scheme to program mathemagical computers, you insist there are no numbers greater than what can be represented by a signed $32$-bit integer, namely the prime P = 2^{31} - 1. Of course, there must be nothing your computers cannot count. In fact, you dislike this upper limit $P$ so much that you have decided to make a new mathemagics where $P$ equals $0$. Ha, take that! (Well, you are quite aware that you are really just counting modulo $P$, but it will have to suffice until you find better ways of punishing $P$.) In fact, this turns out to be quite an advantage for you! For instance, if the number of code permutations you have to check turns out to be 2^{31}, there will actually be just one permutation for you to check, since 2^{31} \bmod P = 1. (Or at least you think so...) That's just magnificent!