这是一场编程竞赛吗？

给定一个素数 $p$ 以及两个剩余系 $0$ 到 $p-1$ 的子集 $S$ 和 $V$。

你的任务是找到满足以下方程组的数对 $(a, b)$ 的数量：

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

所有运算均在模 $p$ 意义下进行。注意，当 $a \neq b$ 时，数对 $(a, b)$ 和 $(b, a)$ 被视为不同的数对。 不允许除以零：当两个分母中的任何一个为零时，该同余式被视为不成立。

输入格式

第一行包含一个整数 $p$ ($2 \le p \le 10^6$，$p$ 为素数)。 第二行包含一个整数 $n$：集合 $S$ 的大小 ($0 \le n \le p$)。 第三行包含 $n$ 个不同的整数 $S_1, S_2, \dots, S_n$：集合 $S$ 的元素 ($0 \le S_i \le p-1$)。 第四行包含一个整数 $m$：集合 $V$ 的大小 ($0 \le m \le p$)。 第五行包含 $m$ 个不同的整数 $V_1, V_2, \dots, V_m$：集合 $V$ 的元素 ($0 \le V_i \le p-1$)。

输出格式

输出一个整数：满足条件的解的数量。

样例

输入 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