res=1
while b:
  if b%2==1:
    res=(res*a)%c
    a=(a**2)%c
    b//=2
  elif b%2==0:
    a=(a**2)%c
    b//=2

# a-это основание   ;  b-это показатель  ;  c-то ,на что делится с остатком