#P1139D. Steps to One
Steps to One
Description
Vivek initially has an empty array and some integer constant .
He performs the following algorithm:
- Select a random integer uniformly in range from to and append it to the end of .
- Compute the greatest common divisor of integers in .
- In case it equals to , break
- Otherwise, return to step .
Find the expected length of . It can be shown that it can be represented as where and are coprime integers and . Print the value of .
The first and only line contains a single integer ().
Print a single integer — the expected length of the array written as .
Input
The first and only line contains a single integer ().
Output
Print a single integer — the expected length of the array written as .
Samples
Note
In the first example, since Vivek can choose only integers from to , he will have after the first append operation, and after that quit the algorithm. Hence the length of is always , so its expected value is as well.
In the second example, Vivek each time will append either or , so after finishing the algorithm he will end up having some number of 's (possibly zero), and a single in the end. The expected length of the list is .