LowbieH and Wtd are both math lovers. One day, LowbieH receives a letter of challenge from Wtd. The letter says, "Let's have a competition on number theory!" Here's the problem of their race:
Define \(f(n)=\sum_{d|n}d[gcd(d,\frac{n}{d})==1]\), for given integer \(n\), please calculate \(S(n)=\sum_{i=1}^n f(i)\) and print the result mod \(10^9+7\).
LowbieH solves the problem easily, while Wtd is still puzzling over it. Can you help Wtd to figure it out?