We need to find $a^{n \choose r} \% M$ where $M$ is prime number.
Problem is ${n \choose r}$ can be really large to store in integer data type (or long long in c++) so i need to calculate ${n \choose r}\%M$ which i know how to do. I also know how to compute $a^b$ in $O(log b)$ time complexity using exponentiation technique.
I am guessing (failed to prove) :
$a^{n \choose r} \% M = a^{{n \choose r}\%M}\%M$. (?)
It looks good on small numbers but can't really prove or disprove it.
Can anybody confirm if its true, if it isn't any alternative to compute my original expression?