Many of you have probably had some contact with cryptography (don’t worry if you haven’t, though, no deep knowledge of cryptography is needed here). In this problem, we will concern ourselves with an encryption scheme consisting of a composition of two different ciphers, a so called permutation cipher, and a so called substitution cipher. In a permutation cipher of block length n, we choose as a secret key a permutation π = π1 π2 . . . πn of the integers 1 to n. We then encrypt a block of n symbols by permuting them according to π, i.e. the encryption of a = a1a2 ...an would be aπ1 aπ2 ...aπn . The substitution cipher, on the other hand, concerns itself with the alphabet of the symbols we use to encode a message. Let the size of the alphabet be m, and assume without loss of generality that the m symbols of the alphabet are the integers 1 to m. We then choose a permutation τ = τ1 τ2 . . . τm of the alphabet, and simply encrypt a symbol ai by τai , i.e. we substitute each symbol according to the permutation τ. Composing these two ciphers is straight-forward; simply do both the permutation of the symbols according to π, and the substitution of the symbols according to τ. Breaking this combined cipher is usually (slightly) more difficult than breaking either one of the two simpler ciphers. Peter is a clever kid with a very limited memory, and he would like to have the combined strength of these two ciphers while only having to remember one permutation as his secret key, rather than two. He has realised that the two different steps are (in some vague sense) independent, and has thus gotten the idea to consider the special case of the above scheme where n = m, and τ = π−1 (the inverse of π; simply choosing τ = π seems too risky, even for Peter). This way, he only has one permutation to remember, while still getting both the permutation step and the substitution step. Asanexample,considerusingn=m=5,andthepermutationπ=42135. Theinverseτ ofπ is 3 2 4 1 5. Take the message block 2 5 3 4 2. Applying the permutation cipher (with secret key π) transforms the message to 4 5 2 3 2, and applying the substitution cipher (with secret key τ) gives 1 5 2 4 2, which is the encryption of the message 2 5 3 4 2 using Peter’s scheme (with secret key π = 4 2 1 3 5). However, you, being an even more clever kid than Peter, doubt the security of Peter’s new scheme, and as a step in investigating this, you should write a program which, given an encrypted block, determines the number of possible inputs which could have been encrypted to that block (assuming that any key is possible). Input Input consists of several test cases. Each test case begins with an integer 1 ≤ n ≤ 50, denoting both the length of an input block and the size of the alphabet. Then follows a line containing n integers between 1 and n, representing the encryption of some input block. Input is terminated by a case where n = 0. Output For each test case, output a line containing the number of different inputs that could have been used. You may assume that the answer will fit in a 64-bit signed integer. Sample Input 5
2/2 12345 5 22222 5 32522 0 Sample Output 1 5 120