Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Question

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that satisfy the equation

$$a^2 + b^3 = c^4 \mod n\,,$$

where $a,b,c \in\{0,1,....,n-1\}$ and $n$ is any natural number.

Does anybody have any idea how to do this? Obviously checking all values yields $O(n^2)$ time.

I am able to compute the triples for a given value of $c$ within the desired bound since you can build a BST in $O(n\log n)$ time where the keys are the particular modulo values in $b^3$ and the values are the number of instances they appear. Then by calculating $((c^4 \!\!\mod n) + n - (a^2 \!\!\mod n)) \!\!\mod n$ for every value of $a$ and doing a search for that key in $b$ we achieve the desired runtime.

How can I achieve the same result for every value of $c$ rather than a specific one though?

I presume the $O(n\log n)$ run-time comes from some form of binary search, sorting or binary search tree but I am not sure exactly how to achieve this for all the values of $c$ rather than a specific one. Any help is appreciated. Thank you.