Fastest way to calculate $a^\binom{n}{r}\bmod M$ if $\binom{n}{r}$ is very large

Question

What is the fastest way to calculate $a^\binom{n}{r} \bmod M$? Here $M$ is a prime number.

So far the best approach I can get is to use $\binom{n}{r}=\binom{n-1}{r-1} + \binom{n-1}{r}$ and then apply product rule of modulo calculation. And I also use Dynamic approach to store calculated result but still this method take time of order Big-$O(n\cdot r)$. And I want faster than this (like logarithmic order). Is it possible?