Test Data Generation

生成测试数据并非简单的任务！生成大的随机数据通常不能够完全保证解法的正确性。 举个例子，考虑以前 Codeforces round 的一道题。它的输入格式如下： > 第一行是一个整数 $n(1\leq n \leq max_n)$ 表示集合的大小，第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n(1\leq a_i\leq max_a)$ 表示集合中的元素，升序排列。 如果你不注意题目的解法，看起来生成一个好的测试数据是非常容易的。令 $n=max_n$，从 $1\sim max_a$ 中生成 $n$ 个不相同的数，并排序。但是马上你就会知道这不那么简单。 下面是这道题目的真实解法。令 $g$ 为 $a_1,a_2,\dots,a_n$ 的最大公约数，令 $x=a_n/g-n$，如果 $x$ 是奇数输出 `Alice`，如果 $x$ 是偶数输出 `Bob` 考虑这道题两个错误的解法，它们与正解只在计算 $x$ 中不同。 第一个解法令 $x = a_n/g$ （不减去 $n$） 第二个解法令 $x=a_n-n$（不除以 $g$） 如果一个测试数据令这两个解法**都**输出错误的答案，称这个数据是有趣的。 给定 $max_n, max_a, q$ 求满足限制且有趣的测试数据的数量对 $q$ 取模的结果。 $1\leq max_n\leq 30000, max_n\leq max_a\leq 10^9, 10^4\leq q\leq 10^5+129$

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 $ .

The only line contains three integers $ max_{n} $ , $ max_{a} $ and $ q $ ( $ 1<=max_{n}<=30000 $ ; $ max_{n}<=max_{a}<=10^{9} $ ; $ 10^{4}<=q<=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 $ .

3 6 100000

4

6 21 100129

154

58 787788 50216

46009

In the first example, interesting test cases look as follows: `<br></br>1 1 1 3<br></br>2 4 6 2 4 6<br></br>`