Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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 of Rasta - lover pairs modulo 109 + 7.
Subtasks 4 - 6:
A 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.
For 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).
If M is equal to for a given A, then you have to calculate M modulo 109 + 7.
Subtasks:
Subtask A1: n = 1234
Subtask A2: n = 1111151
Subtask A3: n = 1234567
Subtask A4: A = 1234
Subtask A5: A = 12345
Subtask A6: A = 1234567
Input
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.