시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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