{"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}^+ $.  \n\nA pair $ (p, q) $ is **Rasta-lover** if:  \n- $ 1 \\leq p, q < n $,  \n- $ \\exists x \\in \\mathbb{Z}^+ $ such that $ p^x \\equiv q \\pmod{n} $.  \n\nA number $ p $ is **$ n $-Rastaly** if:  \n- $ 1 \\leq p < n $,  \n- $ \\gcd(p, n) = 1 $,  \n- $ \\exists x \\in \\mathbb{Z}^+ $ such that $ p^x \\equiv 1 \\pmod{n} $.  \n\nDefine $ f(n) $ as the smallest positive integer $ a $ such that for every $ n $-Rastaly $ p $, $ p^a \\equiv 1 \\pmod{n} $.  \n\n**Constraints**  \n- For subtasks 1–3: Input is $ n $, $ 1 \\leq n \\leq 10^6 $.  \n- For subtasks 4–6: Input is $ A $, $ 1 \\leq A \\leq 10^{18} $, and $ M = f(A) $.  \n\n**Objective**  \n- For subtasks 1–3: Count the number of Rasta-lover pairs modulo $ 10^9 + 7 $.  \n- For subtasks 4–6: Compute $ M = 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, compute f(n) mod (10^9+7), where f(n) is the smallest a such that p^a ≡ 1 (mod n) for all p coprime to n and p < n.  \nInput is either n (for subtasks 1-3) or A (for subtasks 4-6).  \nOutput answer mod 10^9+7.","has_page_source":false}