F. Test Data Generation

Codeforces

IDCF806F

Time5000ms

Memory256MB

Difficulty—

dp

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_. ## Input 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). ## 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_. [samples] ## Note In the first example, interesting test cases look as follows: 1 1 1 3 2 4 6 2 4 6

Samples

Input #1

3 6 100000

Output #1

Input #2

6 21 100129

Output #2

Input #3

58 787788 50216

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Test Data Generation",
    "description": {
      "content": "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 Co",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF806F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nFor example, consider a problem from an old Co...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments