CF773F.Test Data Generation

Test data generation is not an easy task! Often, generating big random test cases is not enough to ensure thorough testing of solutions for correctness.

For example, consider a problem from an old Codeforces round. Its input format looks roughly as follows:

The first line contains a single integer n (1 ≤ n ≤ max__n) — the size of the set. The second line contains n distinct integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ max__a) — the elements of the set in increasing order.

If you don't pay attention to the problem solution, it looks fairly easy to generate a good test case for this problem. Let n = max__n, take random distinct a__i from 1 to max__a, sort them... Soon you understand that it's not that easy.

Here is the actual problem solution. Let g be the greatest common divisor of _a_1, _a_2, ..., a__n. Let x = a__n / g - n. Then the correct solution outputs "Alice" if x is odd, and "Bob" if x is even.

Consider two wrong solutions to this problem which differ from the correct one only in the formula for calculating x.

The first wrong solution calculates x as x = a__n / g (without subtracting n).

The second wrong solution calculates x as x = a__n - n (without dividing by g).

A test case is interesting if it makes both wrong solutions output an incorrect answer.

Given max__n, max__a and q, find the number of interesting test cases satisfying the constraints, and output it modulo q.

测试数据生成并非易事！通常，仅生成大型随机测试用例不足以确保对解法正确性的充分测试。

例如，考虑某场旧 Codeforces 比赛中的一道题目。其输入格式大致如下：

第一行包含一个整数 $n$（$1 \leq n \leq \text{max\_n}$）——集合的大小。第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq \text{max\_a}$）——按升序排列的集合元素。

若未仔细分析该题的正确解法，乍看之下为本题生成良好的测试用例似乎相当简单：令 $n = \text{max\_n}$，从 $1$ 到 $\text{max\_a}$ 中随机选取 $n$ 个互不相同的 $a_i$，再将其排序……但很快你便会意识到，事情远非如此简单。

该题的实际正确解法如下：令 $g$ 为 $a_1, a_2, \dots, a_n$ 的最大公约数；令 $x = a_n / g - n$。则正确解法输出 "Alice" 当且仅当 $x$ 为奇数，输出 "Bob" 当且仅当 $x$ 为偶数。

现考虑两个错误解法，它们仅在计算 $x$ 的公式上与正确解法不同。

第一个错误解法将 $x$ 计算为 $x = a_n / g$（未减去 $n$）。

第二个错误解法将 $x$ 计算为 $x = a_n - n$（未除以 $g$）。

若一个测试用例使得上述两个错误解法均输出错误答案，则称其为有趣的测试用例。

给定 $\text{max\_n}$、$\text{max\_a}$ 和 $q$，求满足约束条件的有趣测试用例的数量，并将结果对 $q$ 取模后输出。

The only line contains three integers max__n, max__a and q (1 ≤ max__n ≤ 30 000; max__n ≤ max__a ≤ 109; 104 ≤ q ≤ 105 + 129).

唯一一行包含三个整数 $\text{max\_n}$、$\text{max\_a}$ 和 $q$（$1 \le \text{max\_n} \le 30\,000$；$\text{max\_n} \le \text{max\_a} \le 10^9$；$10^4 \le q \le 10^5 + 129$）。

Output a single integer — the number of test cases which satisfy the constraints and make both wrong solutions output an incorrect answer, modulo q.

输出一个整数——满足约束条件且使两种错误解法均输出错误答案的测试用例数量，对 $ q $ 取模。

In the first example, interesting test cases look as follows:

1 1 1 3
2 4 6 2 4 6

在第一个例子中，有趣的测试用例如下所示：

1 1 1 3
2 4 6 2 4 6