Sum of largest prime factors revisited

Let $f(n)$ be the largest prime factor of $n$. For example $f(1)=0$, $f(6)=3$ and $f(30)=5$.

Define $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)$.

You are given $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$.

Find $S(9,{10}^9)mod{10}^9$.

---

Thanks to baihacker for the idea.

This problem was inspired by Problem 642 at Project Euler (https://projecteuler.net/problem=642)