{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"Each 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."},{"iden":"output","content":"Print the answer modulo 109 + 7 in one line."},{"iden":"examples","content":""}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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}^+ : p^x \\equiv q \\pmod{n} \\} $.  \nLet $ S(n) = \\{ p \\in \\mathbb{Z}^+ \\mid 1 \\leq p < n \\land \\gcd(p, n) = 1 \\land \\exists x \\in \\mathbb{Z}^+ : p^x \\equiv 1 \\pmod{n} \\} $.  \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 $, $ 1 \\leq n \\leq 10^9 $.  \n- For subtasks 4–6: Input is $ A $, $ 1 \\leq A \\leq 10^9 $.  \n\n**Objective**  \n- For subtasks 1–3: Compute $ |R(n)| \\mod (10^9 + 7) $.  \n- For subtasks 4–6: Compute $ f(A) \\mod (10^9 + 7) $.","simple_statement":"Given n, count the number of pairs (p, q) with 1 ≤ p, q < n such that p^x ≡ q (mod n) for some positive integer x.  \nOr, given A, find the smallest positive integer a such that for every p coprime to n with p < n, p^a ≡ 1 (mod n), then output a mod (10^9+7).","has_page_source":false}