Генерация тестов — непростое дело! Часто генерации случайных больших тестов недостаточно, чтобы обеспечить полноценную проверку решений на правильность.
Например, рассмотрим задачу с одного из прошедших раундов Codeforces. Формат ее входных данных выглядит примерно так:
В первой строке записано целое число n (1 ≤ n ≤ maxn) — количество элементов в множестве. Во второй строке в возрастающем порядке записано n различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ maxa) — элементы множества.
Если не обращать внимания на решение задачи, кажется, что сгенерировать хороший тест очень просто. Возьмем n = maxn, возьмем случайные различные ai от 1 до maxa, отсортируем... Далее вы поймете, что это не совсем так.
Решение задачи выглядит следующим образом. Пусть g — наибольший общий делитель a1, a2, ..., an. Пусть x = an / g - n. Тогда правильное решение выводит «Alice», если x нечетно, и «Bob», если x четно.
Рассмотрим два неверных решения задачи, отличающихся от правильного только формулой вычисления величины x.
Первое вычисляет x по формуле x = an / g (без вычитания n).
Второе вычисляет x по формуле x = an - n (без деления на g).
Будем считать тест интересным, если на нем оба неверных решения выдают ответ, отличающийся от правильного.
По данным значениям maxn, maxa и q найдите количество удовлетворяющих ограничениям интересных тестов к задаче и выведите его по модулю q.
Выходные данные
Выведите единственное число — количество удовлетворяющих ограничениям тестов, на которых оба приведенных неверных решения выдают ответ, отличающийся от правильного, по модулю q.