101 - ZOJ Monthly, December 2010 - I
Nobita wants to send a letter to Shizuka. But he's afraid that Takeshi or Suneo will get the letter and inspect it. So he turns to Doraemon for help. Doraemon takes out a machine from his pocket, and says that it can be used to encrypt his letter.
Here is the encryption process. First, the substitution table should be setup. Suppose the language that Nobita uses has N symbols. So the substitution table will have N entries, the i-th entry is ai, meaning the i-th symbol should be substituted by the ai-th symbol. Input the plain text, the machine will substituted all the symbols in the text using the substitution table. When all the substitutions are finished, the machine will output the encrypted text.
Nobita gets the machine and starts to operate it immediately. But he is so careless that he may setup the substitution in a wrong way. Therefore, there may be ai=aj when i≠j.
In order to guarantee the security, he may encrypt the letter for several times. He wonders how many different texts he can get after sequence of encryptions (including the original text).
There are multiple cases.
For each case, the first line is the size of the substitution table N (2 ≤ N ≤ 100000).
For each case, output the number of the different texts Nobita can get in one line. Since the answer may be very large, you are only asked to output its value mod 1000000007.
3 1 2 0 3 0 1 2 3 1 1 1 3 0 1 2
Doraemon suggests that you should use scanf to read data.
Author: ZHOU, Yilun
Contest: ZOJ Monthly, December 2010