重温最大素因数之和

令 $f(n)$ 为 $n$ 的最大质因数。例如 $f(1)=0$、$f(6)=3$ 和 $f(30)=5$。

定义 $S(k,n)=\sum _{x_1=1}^n\sum _{x_2=1}^n\cdots \sum _{x_k=1}^{n}f(\prod _{i=1}^k{x}_i)$。

给定 $S(2,3)$ = $f(1\times 1)$ + $f(1\times 2)$ + $f(1\times 3)$ + $f(2\times 1)$ + $f(2\times 2)$ + $f(2\times 3)$ + $f(3\times 1)$ + $f(3\times 2)$ + $f(3\times 3)$ = $21$、$S(3,10)=4790$、$S(6,10)=5697722$。

找到$S(9,{10}^9)mod{10}^9$。

---

感谢 百黑客 为了这个想法。

这个问题的灵感来自 Project Euler 的 Problem 642 (https://projecteuler.net/problem=642)