Solution 1. The answer is $f(p) \equiv 0 \bmod 3$ for $p=3, f(p) \equiv 1 \bmod 3$ for $p=3 k+1$, and $f(p) \equiv-1 \bmod 3$ for $p=3 k-1$. The case $p=3$ is already considered, let further $p \neq 3$. For a residue $i$ modulo $p$ denote by $a_{i}(k)$ the number of Flea strategies for which she is at position $i$ modulo $p$ after $k$ minutes. Then $f(p)=a_{0}(p-1)$. The natural recurrence is $a_{i}(k+1)=a_{i-1}(k)+a_{i}(k)+a_{i+1}(k)$, where the indices are taken modulo $p$. The idea is that modulo $p$ we have $a_{0}(p) \equiv 3$ and $a_{i}(p) \equiv 0$. Indeed, for all strategies for $p$ minutes for which not all $p$ actions are the same, we may cyclically shift the actions, and so we partition such strategies onto groups by $p$ strategies which result with the same $i$. Remaining three strategies correspond to $i=0$. Thus, if we denote $x_{i}=a_{i}(p-1)$, we get a system of equations $x_{-1}+x_{0}+x_{1}=3, x_{i-1}+x_{i}+x_{i+1}=0$ for all $i=1, \ldots, p-1$. It is not hard to solve this system (using the 3 -periodicity, for example). For $p=3 k+1$ we get $\left(x_{0}, x_{1}, \ldots, x_{p-1}\right)=(1,1,-2,1,1,-2, \ldots, 1)$, and $\left(x_{0}, x_{1}, \ldots, x_{p-1}\right)=(-1,2,-1,-1,2, \ldots, 2)$ for $p=3 k+2$. Solution 2. Note that $f(p)$ is the constant term of the Laurent polynomial $(x+1+1 / x)^{p-1}$ (the moves to right, to left and staying are in natural correspondence with $x, 1 / x$ and 1.) Thus, working with power series over $\mathbb{F}_{p}$ we get (using the notation $\left[x^{k}\right] P(x)$ for the coefficient of $x^{k}$ in $P$ ) $$\begin{aligned} f(p)=\left[x^{p-1}\right]\left(1+x+x^{2}\right)^{p-1} & =\left[x^{p-1}\right]\left(1-x^{3}\right)^{p-1}(1-x)^{1-p}=\left[x^{p-1}\right]\left(1-x^{3}\right)^{p}(1-x)^{-p}\left(1-x^{3}\right)^{-1}(1-x) \ = & {\left[x^{p-1}\right]\left(1-x^{3 p}\right)\left(1-x^{p}\right)^{-1}\left(1-x^{3}\right)^{-1}(1-x)=\left[x^{p-1}\right]\left(1-x^{3}\right)^{-1}(1-x) } \end{aligned}$$ and expanding $\left(1-x^{3}\right)^{-1}=\sum x^{3 k}$ we get the answer.