  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\nolimits_{m=0}^n m^p H_m^t$, where $H_m$ are harmonic numbers.
When $t\le 4$ these sums were first studied by Spie\ss\ 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 $t\ge 0$.
