Идея такая (не проверял):

Составим вектор-столбец B размера n из нулей. Но на b-й позиции еденица.

Тогда ответ — это a-е число вектора A1 * A2 * ... * Am * B.

Заметим, что это можно считать не слева направо, а справа налево.

Тогда сложность будет в n раз меньше. Вроде ничего не упустил.