Auto comment: topic has been updated by caiocandido (previous revision, new revision, compare).

Let S = 1 * a + 2 * a^2 + 3 * a^3 + ... + n * a^n   ... i
Then, a*S = 1*a^2 + 2*a^3 + ... + n*a^(n+1)         ... ii
Subtracting ii from i gives :-
(1-a)S = (a + a^2 + ... + a^n) - n*a^(n+1)
S = [(a + a^2 + ... + a^n) - n*a^(n+1)] / (1-a)

x1 = (a + a^2 + ... + a^n) = a*(1-a^(n-1))/(1-a)  (sum of geometric progression), &
x2 = n*a^(n+1)
So, the problem basically reduces to finding x^y which can be solved in O(log y) . 

FFT obviously!

You can get the desired series by differentiating the general geometric sum formula and then multiplying both side by a —

Also, this can be helpful somewhere (for example - 908D - New Year and Arbitrary Arrangement) -