{"problem":{"name":"A5. Rasta-lover Pair","description":{"content":"A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that: px ≡ q (modn) Subtasks 1 - 3:  Given n, calculate the number o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070A5"},"statements":[{"statement_type":"Markdown","content":"A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:\n\npx ≡ q (modn)\n\nSubtasks 1 - 3: \n\nGiven n, calculate the number of Rasta - lover pairs modulo 109 + 7.\n\nSubtasks 4 - 6:\n\nA positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.\n\nFor a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).\n\nIf M is equal to  for a given A, then you have to calculate M modulo 109 + 7.\n\nSubtasks:\n\nEach subtask consists of one testcase.\n\nInput consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.\n\nPrint the answer modulo 109 + 7 in one line.\n\n## Input\n\nEach subtask consists of one testcase.Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.\n\n## Output\n\nPrint the answer modulo 109 + 7 in one line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ R(n) = \\{ (p, q) \\in \\mathbb{Z}^2 \\mid 1 \\leq p, q < n \\land \\exists x \\in \\mathbb{Z}^+ \\text{ s.t. } p^x \\equiv q \\pmod{n} \\} $ be the set of Rasta-lover pairs.  \nLet $ S(n) = \\{ p \\in \\mathbb{Z}^+ \\mid 1 \\leq p < n \\land \\gcd(p, n) = 1 \\land \\exists x \\in \\mathbb{Z}^+ \\text{ s.t. } p^x \\equiv 1 \\pmod{n} \\} $ be the set of $ n $-Rastaly numbers.  \nLet $ f(n) = \\min \\{ a \\in \\mathbb{Z}^+ \\mid \\forall p \\in S(n),\\ p^a \\equiv 1 \\pmod{n} \\} $.\n\n**Constraints**  \n- For subtasks 1–3: Input is $ n $, compute $ |R(n)| \\mod (10^9 + 7) $.  \n- For subtasks 4–6: Input is $ A $, compute $ f(A) \\mod (10^9 + 7) $.\n\n**Objective**  \nGiven input $ X $:  \n- If $ X $ corresponds to subtasks 1–3: output $ |R(n)| \\mod (10^9 + 7) $.  \n- If $ X $ corresponds to subtasks 4–6: output $ f(A) \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070A5","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}