Modular Exponentiation by Repeated Squaring

Suppose we are given $\alpha_1, \alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n$ and exponents $e_1, e_2,\ldots, e_k$ where the binary length of the $e_i$ is at most $\ell$. Show how to compute $\beta:= \alpha_1^{e_1}\alpha_2^{e_2}\cdots \alpha_k^{e_k}$ using at most $\ell$ squarings and $\ell+2^k$ multiplications.
Just in case: if the binary length of $e$ is $\ell$, using repeated squaring to compute $\alpha^e\pmod{n}$ uses at most $\ell$ squarings and $\ell$ multiplications.
I tried a few things that makes the computation somewhat more efficient, but I am unable to stay within the multiplication bound. For example, if $e_1$ is the smallest exponent, then we can look at $(\alpha_1\alpha_2\cdots \alpha_k)^{e_1} \alpha_2^{f_2}\cdots \alpha_k^{f_k}$, where $f_i=e_i-e_1$. Then we can precompute $\alpha_1\alpha_2\cdots \alpha_k$ at the cost of $k-1$ multiplications, then use repeated-squaring to raise it to the $e_1$, at the cost of (at worst) $\ell$ squarings and $\ell$ multiplications. However, the rest of the terms need to be computed via multiplication, which breaks the $2^k$ bound.