fn quot_range(n: u32, mut f: F) where F: FnMut(u32, u32, u32) { let mut pre = (0, 0); for d in 1.. { let q = n / d; if pre != (0, 0) { let (q, l, r) = (pre.0, q + 1, pre.1); f(l, r, q); } if q < d { break; } pre = (d, q); f(d, d, q); if q == d { break; } } } fn read() -> u32 { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); s.trim().parse().unwrap() } fn main() { let n = read(); const MOD: u64 = 1_000_000_007; let mut ans = 0; quot_range(n, |l, r, q| { let l = l as u64; let r = r as u64; let q = q as u64; let n = n as u64; ans += (r - l + 1) * (q - 1) * (n - 2) % MOD; ans += MOD - (r - l + 1) * (q - 1) * (q - 2) % MOD; }); let k = (n as f64 / (n as f64).ln_1p().ln_1p().max(1f64)).cbrt().powi(2) as u32; let mut memo = vec![0; k as usize + 1]; for b in 2..=k { for c in 2..=(k / b) { let v = (c - 1) as u64; memo[(b * c) as usize] += v; memo.get_mut((b * (c + 1)) as usize).map(|p| *p += MOD - v); } let x = b as usize; memo[x] = (memo[x] + memo[x - 1]) % MOD; } let mut large = vec![0; 1 + (n / k) as usize]; for i in (1..=(n / k)).rev() { let m = n / i; quot_range(m, |l, r, q| { if l > 1 { large[i as usize] += (r - l + 1) as u64 * (q - 1) as u64; } }); large[i as usize] %= MOD; } quot_range(n, |l, r, q| { if q <= 2 { return; } let w = (r - l + 1) as u64; let s = if q <= k { memo[q as usize] } else { large[(n / q) as usize] }; ans += MOD - s * w % MOD; }); ans %= MOD; println!("{}", ans); }