Wondering if anyone knows how to find a generating function or a nice clean formula for
$$\sum_{k=0}^{n} { {n}\choose{k} } (a^k \bmod q)$$
Multiplying by $x^n$ and summing over $n$ gives the below as a generating function, maybe there is a simple form for this?
$$\sum_{k=0}^{\infty} \frac{a^k}{1-x^k}.$$