　$n$ の素因数分解を $n=p_1^{a_1}\times p_2^{a_2}\times \cdots$ と表せば，
$$n^2f(n)=p_1^{2a_1+1}\times p_2^{2a_2+1}\times \cdots$$
である．ここで，
$$1+p+\cdots+p^{2n+1}=\left(1+p^{n+1}\right)\left(1+p+p^2+\cdots +p^n\right)$$
であるから，与式について
$$\dfrac{S\big(n^2f(n)\big)}{S(n)}=\left(1+p_1^{a_1+1}\right)\left(1+p_2^{a_2+1}\right)\cdots$$
が成り立つ．したがって，$k$ が奇数であるのは $n$ が $2$ べきの場合であり，これより 
$$n_{i}=2^{i-1},\quad k_{i}=1+2^{i}$$
である（ただし $k_1=1$）．特に，$k_{4000}\equiv \textbf{108} \pmod{3989}$ である．
公式解説
https://onlinemathcontest.com/contests/somc007/editorial/2660
　正整数 $n$ に対し，$S(n)$ を $n$ の正の約数の総和，$f(n)$ を $n$ に含まれる素因数の総積とします．例えば，
$$S(6)=1+2+3+6=12,\quad f(72)=2\times 3=6$$
です．ただし，$f(1)=1$ とします．このとき，以下の商
$$\dfrac{S\big(n^2f(n)\big)}{S(n)}$$
が整数であり，さらに奇数であるような正整数 $n$ のうち，$i$ 番目に小さいものを $n_i$ とし，そのときの商を $k_i$ とします．$k_{4000}$ を素数 $3989$ で割った余りを求めてください．