{"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 Codeforces round. Its input format looks roughly as follows:\n\n_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**._\n\nIf 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.\n\nHere 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.\n\nConsider two wrong solutions to this problem which differ from the correct one only in the formula for calculating _x_.\n\nThe first wrong solution calculates _x_ as _x_ = _a__n_ / _g_ (without subtracting _n_).\n\nThe second wrong solution calculates _x_ as _x_ = _a__n_ - _n_ (without dividing by _g_).\n\nA test case is interesting if it makes **both** wrong solutions output an incorrect answer.\n\nGiven _max__n_, _max__a_ and _q_, find the number of interesting test cases satisfying the constraints, and output it modulo _q_.\n\n## Input\n\nThe 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).\n\n## Output\n\nOutput a single integer — the number of test cases which satisfy the constraints and make both wrong solutions output an incorrect answer, modulo _q_.\n\n[samples]\n\n## Note\n\nIn the first example, interesting test cases look as follows:\n\n1              1              1              3\n2              4              6              2 4 6","is_translate":false,"language":"English"}],"meta":{"iden":"CF806F","tags":["dp"],"sample_group":[["3 6 100000","4"],["6 21 100129","154"],["58 787788 50216","46009"]],"created_at":"2026-03-03 11:00:39"}}