跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0888. Test Data Generation

  • ID: 894
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 组合数学
  • 分治
  • 动态规划
  • FFT
  • 数学
  • 数论
  • 算法思想
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Test Data Generation

题目描述

F. Test Data Generation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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≤maxn)− the size of the set. The second line contains n distinct integers a1,a2,...,an (1≤ai≤maxa)− 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=maxn, take random distinct ai from 1 to maxa, 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 a1,a2,...,an. Let x=an/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=an/g (without subtracting n).

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

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

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

Input

The only line contains three integers maxn, maxa and q (1≤maxn≤30000; maxn≤maxa≤109; 104≤q≤105+129).

Output

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

Examples
Input
3 6 100000
Output
4
Input
6 21 100129
Output
154
Input
58 787788 50216
Output
46009
Note

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


1 1 1 3
2 4 6 2 4 6


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 321 题。保留原作者与原赛事署名。