CF360D.Levko and Sets

Levko loves all sorts of sets very much.

Levko has two arrays of integers _a_1, _a_2, ... , a__n and _b_1, _b_2, ... , b__m and a prime number p. Today he generates n sets. Let's describe the generation process for the i-th set:

1. First it has a single number 1.
2. Let's take any element c from this set. For all j (1 ≤ j ≤ m) if number (c·a__i__b__j) mod p doesn't occur in the set, then add it to the set.
3. Repeat step 2 as long as we can add at least one element to our set.

Levko wonders, how many numbers belong to at least one set. That is, he wants to know what size is the union of n generated sets.

Levko 非常喜欢各种集合。

Levko 有两个整数数组 $a_1, a_2, \ldots , a_n$ 和 $b_1, b_2, \ldots , b_m$，以及一个质数 $p$。今天他生成 $n$ 个集合。下面描述第 $i$ 个集合的生成过程：

1. 最初该集合仅包含一个数 $1$。
2. 任取该集合中的一个元素 $c$；对所有 $j$（$1 \le j \le m$），若数 $(c \cdot a_i^{b_j}) \bmod p$ 不在该集合中，则将其加入集合。
3. 重复步骤 2，直到无法再向集合中添加任何新元素为止。

Levko 想知道：有多少个数至少属于这 $n$ 个生成集合中的一个。即，他想求这 $n$ 个生成集合的并集的大小。

The first line contains three integers n, m and p (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 2 ≤ p ≤ 109), p is prime.

The second line contains space-separated integers _a_1, _a_2, ... , a__n (1 ≤ a__i < p). The third line contains space-separated integers _b_1, _b_2, ... , b__m (1 ≤ b__i ≤ 109).

第一行包含三个整数 $n$、$m$ 和 $p$（$1 ≤ n ≤ 10^4$，$1 ≤ m ≤ 10^5$，$2 ≤ p ≤ 10^9$），其中 $p$ 是质数。

第二行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 ≤ a_i < p$）。
第三行包含 $m$ 个用空格分隔的整数 $b_1,\,b_2,\,\dots,\,b_m$（$1 ≤ b_i ≤ 10^9$）。

The single number — the size of the union of the sets.

单个数字——集合的并集的大小。