Product of coprimes
Hard
Execution time limit is 2 seconds
Runtime memory usage limit is 64 megabytes
You are given a positive integer m. Calculate the product of all positive integers less then or equal to m and coprime with m, and give the answer modulo m.
Input
The only line of input file contains a positive integer m ≤ 10^18.
Output
In the output file you should write the answer to the task.
Examples
Input #1
Answer #1
Submissions 870
Acceptance rate 8%