306055: CF1139D. Steps to One
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Steps to One
题意翻译
给一个数列,每次随机选一个 $1$ 到 $m$ 之间的数加在数列末尾,数列中所有数的 $\gcd=1$ 时停止,求期望长度。题目描述
Vivek initially has an empty array $ a $ and some integer constant $ m $ . He performs the following algorithm: 1. Select a random integer $ x $ uniformly in range from $ 1 $ to $ m $ and append it to the end of $ a $ . 2. Compute the greatest common divisor of integers in $ a $ . 3. In case it equals to $ 1 $ , break 4. Otherwise, return to step $ 1 $ . Find the expected length of $ a $ . It can be shown that it can be represented as $ \frac{P}{Q} $ where $ P $ and $ Q $ are coprime integers and $ Q\neq 0 \pmod{10^9+7} $ . Print the value of $ P \cdot Q^{-1} \pmod{10^9+7} $ .输入输出格式
输入格式
The first and only line contains a single integer $ m $ ( $ 1 \leq m \leq 100000 $ ).
输出格式
Print a single integer — the expected length of the array $ a $ written as $ P \cdot Q^{-1} \pmod{10^9+7} $ .
输入输出样例
输入样例 #1
1
输出样例 #1
1
输入样例 #2
2
输出样例 #2
2
输入样例 #3
4
输出样例 #3
333333338