In this note, we extend the definition of multiple harmonic sums and apply their stuffle relations to obtain explicit evaluations of the sums $R_n(p,t)=sum olimits_{m=0}^n m^p H_m^t$, where $H_m$ are harmonic numbers. When $tle 4$ these sums were first studied by Spiess around 1990 and, more recently, by Jin and Sun. Our key step first is to find an explicit formula of a special type of the extended multiple harmonic sums. This also enables us to provide a general structural result of the sums $R_n(p,t)$ for all $tge 0$.