D. Левко и множества
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Левко очень любит различные множества.

У Левко есть два массива целых чисел a1, a2, ... , an и b1, b2, ... , bm и простое число p. Сегодня он генерирует n множеств. Опишем процесс генерации i-ого множества:

  1. Сначала в нем находится единственное число 1.
  2. Возьмем любой элемент c из этого множества. Для всех j (1 ≤ j ≤ m), если числа (c·aibj) mod p нет в этом множестве, то добавим его туда.
  3. Повторяем пункт 2 пока можем добавить хотя бы один элемент в наше множество.

Левко очень интересно сколько чисел принадлежат хотя бы одному множеству. Другими словами он хочет найти размер объединения n сгенерированных множеств.

Входные данные

В первой строке записаны три целых числа n, m и p (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 2 ≤ p ≤ 109), p — простое.

Во второй строке через пробел записаны числа a1, a2, ... , an (1 ≤ ai < p). В третьей строке через пробел записаны числа b1, b2, ... , bm (1 ≤ bi ≤ 109).

Выходные данные

Единственное число — размер объединения множеств.

Примеры
Входные данные
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