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

输入输出样例

输入样例 #1

3 6 100000

输出样例 #1

4

输入样例 #2

6 21 100129

输出样例 #2

154

输入样例 #3

58 787788 50216

输出样例 #3

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>`