The return of Brilli

I don't know how to do this without a computer. Brilli has $24$ different points to choose from at each step.

My approach was to write down all the three-step paths that Brilli could take which started at the origin and didn't touch the origin again. I found $13\text{,}056$ such paths (there were a total of $24^3$ paths, of which $768$ touched the origin too early--at least I can verify that part without a computer), and there were $624$ endpoints. Then the answer was $\sum\limits_{i=1}^{624} n_i^2,$ where $n_i$ is the number of such paths ending in a point $p_i.$

So I got $725\text{,}568.$

I'd be interested to hear of other solutions.