When I put in Python interpreter a ** b % c with large a (20 figures) b (4 figures) c (20 figures) I saw that Python calculates it pretty fast, almost like pow (a,b,c). I expect another behavior that Python first calculate a ** b then get the modulo (%) of result and such calculation will take significantly more time.
Where is the magic behind the scene?
There is no magic behind the scenes, other than Python supports arbitrary-precision integers, and is well-implemented.  It really did calculate a**b, then %c.
Behavior of Python ** and % operators with big numbers