Генерация тестов — непростое дело! Часто генерации случайных больших тестов недостаточно, чтобы обеспечить полноценную проверку решений на правильность.

Например, рассмотрим задачу с одного из прошедших раундов Codeforces. Формат ее входных данных выглядит примерно так:

В первой строке записано целое число n (1 ≤ n ≤ max_n) — количество элементов в множестве. Во второй строке в возрастающем порядке записано n различных целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ max_a) — элементы множества.

Если не обращать внимания на решение задачи, кажется, что сгенерировать хороший тест очень просто. Возьмем n = max_n, возьмем случайные различные a_i от 1 до max_a, отсортируем... Далее вы поймете, что это не совсем так.

Решение задачи выглядит следующим образом. Пусть g — наибольший общий делитель a₁, a₂, ..., a_n. Пусть x = a_n / g - n. Тогда правильное решение выводит «Alice», если x нечетно, и «Bob», если x четно.

Рассмотрим два неверных решения задачи, отличающихся от правильного только формулой вычисления величины x.

Первое вычисляет x по формуле x = a_n / g (без вычитания n).

Второе вычисляет x по формуле x = a_n - n (без деления на g).

Будем считать тест интересным, если на нем оба неверных решения выдают ответ, отличающийся от правильного.

По данным значениям max_n, max_a и q найдите количество удовлетворяющих ограничениям интересных тестов к задаче и выведите его по модулю q.