시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 11 7 3 42.857%

## 문제

Is it a programming contest?

You are given a prime number $p$ and two subsets $S$ and $V$ of residues from $0$ to $p − 1$.

Your task is to find the number of pairs $(a, b)$ that satisfy the following set of equations:

• $\left(\displaystyle\prod_{z \in V}{\left(\frac{\left(2a+3b\right)^2 + 5a^2}{\left(3a+b\right)^2} + \frac{\left(2a+5b\right)^2 + 3b^2}{\left(3a+2b\right)^2} - z\right)}\right) \equiv 0$
• $a \in S$
• $b \in S$

All operations are performed modulo $p$. Note that, when $a \ne b$, the pairs $(a, b)$ and $(b, a)$ are considered different.

Division by zero is not allowed: when any of the two denominators turns into a zero, the congruence is considered false.

## 입력

The first line contains a single integer $p$ ($2 \le p \le 10^6$, $p$ is prime).

The second line contains a single integer $n$: the size of $S$ ($0 \le n \le p$).

The third line contains $n$ distinct integers $S_1, S_2, \dots , S_n$: the elements of $S$ ($0 \le S_i \le p − 1$).

The fourth line contains a single integer $m$: the size of $V$ ($0 \le m \le p$).

The fifth line contains $m$ distinct integers $V_1, V_2, \dots , V_m$: the elements of $V$ ($0 \le V_i \le p − 1$).

## 출력

Print one integer: the number of solutions.

## 예제 입력 1

7
4
0 4 5 6
2
2 3


## 예제 출력 1

8


## 예제 입력 2

19
10
0 3 4 5 8 9 13 14 15 18
10
2 3 5 9 10 11 12 13 14 15


## 예제 출력 2

42