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 7
2
5

3

1 2 7
2
2 4

3

2 1 7
1 6
2

1

2 1 7
1 6
5

2