No tag edit access

F. Test Data Generation

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTest 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*.

Input

The only line contains three integers *max*_{n}, *max*_{a} and *q* (1 ≤ *max*_{n} ≤ 30 000; *max*_{n} ≤ *max*_{a} ≤ 10^{9}; 10^{4} ≤ *q* ≤ 10^{5} + 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2018 08:29:52 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|