BALTIC-WAY 2014 Problem 18

Let $p$ be a prime number, and let $n$ be a positive integer. Find the number of quadruples $\left(a_{1}, a_{2}, a_{3}, a_{4}\right)$ with $a_{i} \in\left\{0,1, \ldots, p^{n}-1\right\}$ for $i=1,2,3,4$ such that

$$p^{n} \mid\left(a_{1} a_{2}+a_{3} a_{4}+1\right) .$$