HMMT 2011 U32

Let $p$ be a prime positive integer. Define a mod- $p$ recurrence of degree $n$ to be a sequence $\left\{a_{k}\right\}_{k \geq 0}$ of numbers modulo $p$ satisfying a relation of the form $a_{i+n}=c_{n-1} a_{i+n-1}+\ldots+c_{1} a_{i+1}+c_{0} a_{i}$ for all $i \geq 0$, where $c_{0}, c_{1}, \ldots, c_{n-1}$ are integers and $c_{0} \not \equiv 0(\bmod p)$. Compute the number of distinct linear recurrences of degree at most $n$ in terms of $p$ and $n$.