One day, when human scientists inspected the Glasses Case Planet, they found a group of Groundhogs living on this seemingly barren planet. This group of Groundhogs had evolved civilization over a long period of time and unified language. Now, the official language of Groundhog is Groundhogish.

 According to a survey of the Groundhogs' society, humans could determine that Groundhogish had   different letters, numbered from to . A sentence in Groundhogish consists of several letters. In Groundhogish, the letter has a value of ,and the value of a sentence is the product of the values of each letter.

 After all the hardships, the human research vessel intercepted a piece of Groundhogish. It contained  letters. However, because of the long age, some letters have been missing, and it is impossible to determine the missing positions and the letters in these positions. However, after conducting a large-scale search and verification, humans had determined that at most letters were missing in this sentense (It was also possible that humans were lucky enough that none of the letters in this sentence were missing).

 Now, as the chief scientist of human research on Groundhog, Apple wants to know the sum of the value of all the possible original texts (that is, the sentences before the letters were missing). Since the number  has a unique meaning to the Groundhogs' society, she wants to know the value modulo . Now, she entrusts you to solve this problem.

输入描述:

The input consists of multiple test cases.
End of input is indicated by a line containing three zeroes.
Each test cases contains three lines.
The first line contains three integers ,and .
The second line contains  integers ranged in  to , and the i-th element is the  letter of the sentence.
The third line contains  integers, and the  integer indicates the values of the  letter(that is,).

输出描述:

For each test case, output one line with a integer indicating the answer modulo .

3 3 1
1 2 3
1 2 3
10 26 50
9 12 15 22 5 1 16 16 12 5
1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8
0 0 0

114
740279225

For the first data case,if we replace  ,, with ,,  ,then we'll get a sentence of .
There are several possible original texts:
1. ，with the value of 
2. ，with the value of 
3. ，with the value of 
4. ，with the value of 
5. ，with the value of 
6. ，with the value of 
7. ，with the value of 
8. ，with the value of 
9. ，with the value of 
10. ，with the value of 
The sum of all the values is .

备注:

The number of data cases    does not exceed 250,and it is promised that  .
There're at most  cases with .