jmc

Let's work backwards. The minimum base-sixteen representation of $g(n)$ that cannot be expressed using only the digits $0$ through $9$ is $A_{16}$, which is equal to $10$ in base 10. Thus, the sum of the digits of the base-eight representation of the sum of the digits of $f(n)$ is $10$. The minimum value for which this is achieved is $37_8$. We have that $37_8=31$. Thus, the sum of the digits of the base-four representation of $n$ is $31$. The minimum value for which this is achieved is $13,333,333,333_4$. We just need this value in base 10 modulo 1000. We get $13,333,333,333_4=3(1+4+4^2+\cdots +4^8+4^9)+4^{10}=3\left(\frac{4^{10}-1}{3}\right)+4^{10}=2\ast 4^{10}-1$. Taking this value modulo $1000$, we get the final answer of $\boxed{151}$.