For given sequence , a sequence has *shape* A if and only if:

* for all ;
* for all .

Given sequence , Bobo would like to know the number of subsequences of length n which have *shape* A modulo .

输入描述:

The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains two integers n and m.
The second line contains n integers .
The thrid line contains m integers .

* The number of test cases does not exceed 10.
* 
* 
* 
* 
*  are distinct.

输出描述:

For each case, output an integer which denotes the number of subsequences modulo .

2 3
0 0
1 2 3
3 5
1 0 1
4 1 3 2 5

3
2

备注:

For the first sample, all three subsequences of length 2 are of shape A.