{"problem":{"name":"B. WA6","description":{"content":"Becoming blue on Codeforces is something to be proud of, especially at the age of ten. The fifth grader Vasya has recently become blue on CF, and to celebrate it he decided to implement a new advance","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10263B"},"statements":[{"statement_type":"Markdown","content":"Becoming blue on Codeforces is something to be proud of, especially at the age of ten.\n\nThe fifth grader Vasya has recently become blue on CF, and to celebrate it he decided to implement a new advanced algorithm that he learnt from cp-algorithms. The algorithm is called \"Modular Multiplicative Inverse\". This algorithm finds the modular multiplicative inverse given a number and a module.\n\nVasya decided to use it to solve a problem on a famous platform for young programmers — Codeforces. The problem goes as follows: given two integers $n$ and $M$ ($1 <= n < M <= 10^9 + 7$), find such a number $k$ that $n dot.op k equiv 1 (mod M)$; $1 <= k < M$; $M$ is a prime. \n\nThanks to the article mentioned above, Vasya knows that it is enough to raise $n$ to the power of $M -2$ modulo $M$ to obtain the answer, and, of course, he didn't bother to prove this. Vasya quickly implemented the code for that problem. However, he became discouraged as soon as his wonderful solution got WA6. Feeling deeply offended, he deleted his code and decided to rage quit competitive programming. Nevertheless, on the next day he didn't get any homework and decided to recover his code and find the bugs.\n\nHelp Vasya recover his incorrect solution!\n\nTwo integer numbers, separated by space: $n$ and $M$, $1 <= n < M <= 10^9 + 7$.\n\nPrint one integer $k$ — the output of Vasya's program for the given test.\n\n## Input\n\nTwo integer numbers, separated by space: $n$ and $M$, $1 <= n < M <= 10^9 + 7$.\n\n## Output\n\nPrint one integer $k$ — the output of Vasya's program for the given test.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Given integers $n$ and $M$ with $1 \\leq n < M \\leq 10^9 + 7$ and $M$ prime, compute:\n\n$$\nk \\equiv n^{M-2} \\pmod{M}, \\quad \\text{where } 1 \\leq k < M\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10263B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}