at 6:00
how come b=B%(p-1)?
Doubt for b value
Given two large numbers A and B, we have to find A^B % M. A^B can be written as AAA… B times. So we can simply take A%M. But since A is a large number we can store it in a long array and perform modulo digit by digit. Since x*10+y %M = ((x%M)*10 + y)%M we can iteratively do for all digits. Next we note that 10^9+7 is a prime number. According to Fermat’s Little Theorm, A^p-1 ≡ 1 % p , where p is a prime number. Hence we take B%(p-1) => B%(10^9+6)
well ,
you can see my code , its a small one-