Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3454
Nobita's Letter

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 ij.

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).
The second line contains N integers a0, a1 ... aN-1 (0 ≤ ai < N), where ai means the i-th symbol should be substituted by the ai-th symbol.
The third line is the length of the text M (2 ≤ M ≤ 100000).
The fourth line contains M integers b0, b1 ... bM-1 (0 ≤ bi < N), describing the text.


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.

Sample Input

1 2 0
0 1 2
1 1 1
0 1 2

Sample Output



Doraemon suggests that you should use scanf to read data.

Author: ZHOU, Yilun
Contest: ZOJ Monthly, December 2010
Submit    Status