Levko and Sets

题意翻译

有两个整数数组$a_1,a_2......a_n$ 和$b_1,b_2......b_m$ ，与一个质数$p$ ，现在要生成$n$ 个集合，第$i$ 个集合生成方式如下： 1.开始，集合只有元素1 2.从集合中选一个元素$c$ ，对于所有的$j$ ，如果足$c\times a_i^{b_j}\%p$ 不在当前集合，就把它加入集合 3.重复以上步骤 求$n$ 个集合的并的大小 感谢@Fheiwn 提供的翻译

题目描述

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.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ p $ ( $ 1<=n<=10^{4} $ , $ 1<=m<=10^{5} $ , $ 2<=p<=10^{9} $ ), $ 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}<=10^{9} $ ).

输出格式

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

输入输出样例

输入样例 #1

1 1 7
2
5

输出样例 #1

3

输入样例 #2

1 2 7
2
2 4

输出样例 #2

3

输入样例 #3

2 1 7
1 6
2

输出样例 #3

1

输入样例 #4

2 1 7
1 6
5

输出样例 #4

2