
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 ith entry is a_{i}, meaning the ith symbol should be substituted by the a_{i}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 a_{i}=a_{j} 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). InputThere are multiple cases.
For each case, the first line is the size of the substitution table N (2 ≤ N ≤ 100000). OutputFor 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. Sample Input3 1 2 0 3 0 1 2 3 1 1 1 3 0 1 2 Sample Output3 2 HintDoraemon suggests that you should use scanf to read data. Author: ZHOU, Yilun Contest: ZOJ Monthly, December 2010 